一个很好的随机拼图15

Question

我实施了一个难题15，供人们在线竞争。我当前的随机器的工作原理是从良好的配置开始，然后将图块移动100步（任意数）

一切都很好，但是，每过一会儿，瓷砖就会变得太容易洗牌，只需几步就可以解决难题，因此对于某些人以更高的速度获得更好的成绩，游戏确实是不公平的。

什么是将初始配置随机化以免“太容易”的好方法？

Answer 1

您可以生成一个完全随机的配置（可解），然后使用一些求解器来确定最佳移动顺序。如果序列对您来说足够长，那很好，否则请生成新配置并重复。

更新和详细信息

维基百科上有一篇关于15谜题的文章以及何时可以解决（什么时候不可以解决）。简而言之，如果空心正方形位于右下角，则且仅当相对于该元素的反转次数（反转是序列中两个元素的交换，不一定是相邻元素）时，该难题才可解决。目标排列是均匀的。

然后，您可以通过执行偶数次反转来轻松生成可解的开始状态，这可能比通过常规移动更快地导致不那么容易解决的状态，并且可以保证它仍然可解。

实际上，您不需要使用我上面提到的搜索算法，而是可以使用的启发式算法。这样一来总是低估了，永远也不会高估解决难题所需的动作数，即可以保证您不会像试探法那样告诉您更少的动作。

一个好的启发式方法是每个数字到目标位置的曼哈顿距离之和。

摘要

简而言之，一种可能的（非常简单的）算法可以生成起始位置，如下所示：

1: current_state <- goal_state
2: swap two arbitrary (randomly selected) pieces
3: swap two arbitrary (randomly selected) pieces again (to ensure solvability)
4: h <- heuristic(current_state)
5: if h > desired threshold
6:     return current_state
7: else
8:   go to 2.

要绝对确定状态的难度，您需要使用一些求解器找到最佳解决方案。启发式方法只会给您一个估计。