我怎样才能确保当我改变拼图时,我仍然会得到一个均匀的排列？

Question

我有兴趣实现14-15拼图:

我正在按递增的顺序创建一个值为0到15的数组:

S = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

现在,我想要做的就是改变它们以创建一个新的拼图实例.但是,我知道如果我创建一个具有"奇数排列"而不是无法解决的板.

维基百科说我需要创建一个具有均匀排列的拼图.我相信这意味着我只需要确保我进行偶数交换？

我将如何修改Fisher-Yates,以确保我最终得到一个均匀的排列？如果我对数组中的每个元素进行交换,这将是16个交换,我相信这将是一个偶数排列.但是,我是否需要关注自己交换？有没有其他方法可以确保我有一个有效的拼图？

Answer 1

我不会真正尝试改变算法本身，无论如何它对于这个应用程序来说可能没有实际意义。据我所知，有两种选择：

1. 只需重新洗牌，直到获得均匀的排列。这可能会平均丢弃一半的排列（好吧，也许更多一点），但额外的工作很可能可以忽略不计。
2. 使用游戏本身的动作来洗牌。也就是说，只需做几百个随机动作。由于您没有取出所有部件并重新组装它们，因此您无法生成无法解决的状态。