artificial-intelligence - 如何用两个空白检查 n-puzzle 是可解的？

Question

我已经修改了关于 n-puzzle 的问题。在这种情况下，拼图有两个空白而不是一个空白。

Initial State
3   5   1   
4   6   -   
7   2   -   


Goal State
-   1   7   
3   2   -   
5   6   4   

有什么算法可以用来做这个吗？

标签： artificial-intelligencea-starsliding-tile-puzzle

Answer 1

所有解决常规滑动拼图难题的现有算法（例如 A* 或 IDA*）也可以解决此变体。具有多个空白的谜题相当于滑动瓷砖谜题的模式数据库- 用空白替换一些块的谜题的精确解决方案可以用作只有一个空白的原始谜题的启发式。

（准确地说，它们相当于加法模式数据库。您可以将几个组合在一起并添加它们的启发式值，只要交换两个空白的动作成本为 0 并且没有任何瓷砖重复。）