我有兴趣实现14-15 谜题：
我正在创建一个值为 0 - 15 的数组，按递增顺序排列：
S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }
现在，我想做的是随机播放它们以创建拼图的新实例。但是，我知道如果我创建一个具有“奇数排列”的棋盘，那么它是无法解决的。
维基百科说我需要用一个均匀的排列来创造这个谜题。我相信这意味着我只需要确保我进行偶数交换？
我将如何修改 Fisher-Yates，以确保最终得到一个均匀排列？如果我对数组中的每个元素进行交换，那将是 16 次交换，我相信这将是一个偶数排列。但是，我是否需要担心与自身交换？有没有其他方法可以确保我有一个有效的谜题？
您应该能够使用 Fischer-Yates。
考虑一个偶数排列 P = x1 x2 .... xn。
Fischer yates 生成 P 的概率为 1/n!。
它以 1/n! 的概率生成 x2 x1 ... xn！
因此，上述过程产生排列 P 的概率是 2/n！= 1/(n!/2)
n!/2 是偶数排列的数量。
因此，上述过程以相同的概率生成偶数排列。
要检查排列是否是偶数：计算排列中反转次数的奇偶性。
这是我在这里找到的已经回答的内容：
“这个问题基本上可以归结为做一个标准的洗牌算法，稍微扭曲一下。
关键的观察是，要解决 15 谜题，排列的奇偶性和空白方块的奇偶性必须相同。
为此，首先使用标准算法创建随机排列。例如 Knuth shuffle 算法：随机排列
使用 Knuth 的 shuffle（或 Fisher-Yates shuffle）的优势在于它涉及交换数字，因此您可以轻松跟踪排列的奇偶性。每个交换要么保持奇偶校验（如果交换 1 & 3 ），或者更改奇偶校验（如果交换 1 & 2 ）。
将空白方块放在与排列的奇偶性相同的奇偶性上，就完成了。如果排列具有奇校验，则将空白放置一个奇数正方形（1,3,5,... 随机选择）。如果排列具有偶数奇偶性，则将空白放在偶数正方形上。”
此外，“实际上，大约每 4 个连续生成的排列将由两个偶数和两个奇数排列组成，因此即使每次迭代的成本也可以忽略不计。”
你也可以看看这个网站：http ://eusebeia.dyndns.org/epermute
我不会真的尝试改变算法本身，无论如何它可能对这个应用程序没有实际意义。据我所知，有两种选择：
Fisher-Yates 取决于将任何元素与任何其他元素交换的能力。由于这违反了拼图的物理原理，我认为您不能在这里使用它。
天真的解决方案是手动执行您会执行的操作，随机选择与空的瓷砖相邻的瓷砖之一并与之交换。我不知道您需要进行多少次交换才能获得良好的洗牌。
更新答案：
在介绍这个算法之前，我需要定义两个术语：反转和极性。
倒置：一对与它们应该在的位置相反的对象。有关反转的更多信息，请参阅计数数组中的反转
谜题的极性是所有瓷砖之间的反转总数是偶数还是奇数。一个有 10 次反转的谜题具有均匀的极性；具有 7 个反转的谜题具有奇数极性。
考虑这样的 3x3 拼图：
| 6 | 3 | 2 |
| .. | 4 | 7 |
| 5 | 1 | 0 |
在这里计算所有反转，我们得到：（i）6 与 0、1、2、3、4 和 5 反转。（ii）3 与 0、1 和 2 反转。（iii）2 与 0 反转并且1. (iv) 4 与 0 和 1 反转。 (v) 7 与 0、1 和 5 反转。 (vi) 5 与 0 和 1 反转。 (vii) 1 与 0 反转。总共有19次反转。
如果拼图的宽度是偶数，则向上或向下移动拼图将反转极性，因此当空拼图在最后一行时拼图具有偶数极性非常重要。为此，我们将把从底行到空瓦的距离添加到我们的总反转中。
现在我们知道，如果一个谜题具有偶数极性（或排列），它是可以解决的。因此，如果我们的极性是偶数，那么我们的问题就解决了，但是对于奇数极性，我们必须这样做：
如果空图块不在第一行，则交换第一行中的前两个相邻图块。这会将极性改变 1，我们将得到具有均匀极性的可解谜题。
但是，如果第一行有空图块，则交换最后一行中的相邻图块。这将使难题可以解决。所以最后你总是以一个可解的谜题告终。
我希望我能满足stackoverflow对这个问题的回答要求。