N-拼图伪随机洗牌？

Question

我正在开发N-Puzzle游戏(也被称为15-Puzzy...)在正方形网格上拆分图像，移除其中的一部分，然后进行混洗。我对这个难题的解决方案不太感兴趣，因为这取决于用户。但我想伪随机地洗牌。

我知道1/2的所有可能的洗牌都会使棋盘无法解决。假设我有一些rand()-esc函数，并且我知道棋盘的大小，有没有一种简单的方法来伪随机地生成一个随机的状态？

我在内存中有一个游戏板，一个整数的多维数组。我的方法只是将图像按相反的顺序放置，将最后一个图像与偶数板上倒数第二个图像交换。我的当前函数如下所示，我正在使用Java。

private void shuffle()
{
    gameState = new int[difficulty][difficulty];
    int i = 0, N = (difficulty * difficulty) -1;

    while (i < N)
        gameState[(int)(i / difficulty)][i % difficulty] = N - ++i;
    gameState[difficulty-1][difficulty-1] = N;

    // N id even when the remainder of N/2 is 0
    if ((difficulty % 2) == 0)
    {
        // swap 2nd to last and 3rd to last element
        int tmpEl = gameState[difficulty-1][difficulty-2];
        if (difficulty == 2)
        {
            gameState[1][0] = gameState[0][1];
            gameState[0][1] = tmpEl;
        }
        else
        {
            gameState[difficulty-1][difficulty-2] = gameState[difficulty-1][difficulty-3];
            gameState[difficulty-1][difficulty-3] = tmpEl;
        }
    }
}

Answer 1

我的建议是跟踪数组中的一个空正方形(您已经移除的部分)。

然后，随机挑选这个空正方形的一边(确保做必要的边界检查)，并用空正方形“交换”那一边的那一块。这模拟了玩家要做的滑动动作。

重复此操作多次(简单难度设置-难度设置您所做的迭代次数)，每次在数组中“滑动”空方块。

使用这种方法，您只需跟踪空正方形的位置，然后选择要移动到的随机边。

希望这能对你有所帮助--我在这里没有提供任何代码，只提供了一个简单的算法供你使用。

Answer 2

这个问题基本上归结为做一个标准的混洗算法和一个小的扭曲。

关键的观察是，对于15个拼图是可解的，排列的奇偶性和空白正方形的奇偶性必须相同。

为此，首先使用标准算法创建一个随机排列。例如，Knuth混洗算法：Random Permutations

使用Knuth's shuffle (或Fisher-Yates shuffle )的优点是它涉及到交换数字，因此您可以轻松地跟踪排列的奇偶校验。每个交换要么保留奇偶校验(如果交换1和3 )，要么更改奇偶校验(如果交换1和2 )。

将空白方块放在与排列的奇偶校验相同的奇偶校验上，就完成了。如果排列具有奇数奇偶校验，则将空白放置一个奇数正方形(1,3,5，...随机选择)。如果排列具有偶数奇偶校验，则将空白放在偶数正方形上。

Answer 3

只需生成随机拼图，直到您生成具有偶数奇偶校验的拼图。http://heuristicswiki.wikispaces.com/N+-+Puzzle