问题标签 [sliding-tile-puzzle]

我正在尝试实现一种方法来防止再次生成 8 个拼图的已访问状态。
我最初的方法是将每个访问过的模式保存在一个列表中，并在每次算法想要生成一个孩子时进行线性检查。
现在我想O(1)通过列表访问及时做到这一点。8 拼图中的每个模式都是 1 到 9 之间数字的有序排列（9 是空白块），例如 125346987 是：

1 2 5
3 4 6
_ 8 7

此类所有可能排列的数量约为 363,000（9！）。将这些数字散列到该大小列表的索引的最佳方法是什么？

我正在尝试测试一个 15 谜题是否可以解决。我写了一个对大多数谜题都有效的方法，但对一些不适用。

例如，这个谜题可以通过两个动作 (0, 11), (0, 12) 来解决

这是更好地可视化的拼图：

但是这个谜题的奇校验是 3，所以不应该是可解的。

我究竟做错了什么？

我正在尝试创建一个程序，该程序将找到解决具有以下规则的难题的步骤：

• 给定 4x4 网格中的任何一组颜色，尝试匹配具有相同颜色数量的结束模式。
• 颜色不会交换，而是水平或垂直旋转，这样

{W，W，B，W}

可以旋转到

{W，W，W，B}

{B，W，W，W}

{W，B，W，W}

• 整个谜题不到 16 个步骤即可解决。

我已经想出了如何存储拼图本身的数据，但我正在努力寻找一个可以显示步骤的解决方案。由于深度限制为 16 步，我可以尝试暴力破解，但真的不知道如何建立模式。

这类似于解决魔方，我已经查看了以下资源：

• stackoverflow.com/questions/34656587/solving-rubiks-cubes-for-dummies/34656726#34656726

• stackoverflow.com/questions/5563671/solving-rubiks-cube-programmatically

• amzi.com/articles/rubik.htm

• chessandpoker.com/rubiks-cube-solution.html

和 15 个数字的问题

• stackoverflow.com/questions/3621623/how-to-programatically-solve-the-15-moving-numbers-puzzle

为了使这个问题尽可能清楚：a) 存储/打印步骤和 b) 找到所需步骤最少的解决方案的好方法是什么？

需要在下图中编号 1 到 8，以便相邻小区中没有两个数字彼此连续模式：

其中每个 * 包含一个 1 到 8 之间的数字，并且没有两个邻居 * 是连续的数字。

我只使用曼哈顿启发式和曼哈顿和线性冲突启发式为 15 谜题编写了 A-star 算法。

我的问题是，对于某些特定的谜题实例，线性冲突是否会导致创建和探索比单独使用 a-Star 的曼哈顿启发式更多的节点？

由于我尝试通过我的程序解决大多数拼图实例，这些实例需要 <50 次移动，只需使用曼哈顿即可在给定内存的适当时间内解决，并将其与线性冲突结合作为启发式更快地解决，因此需要 >50 次移动的实例会导致程序运行无限期地挂断我的机器，但是对于一个需要 42 次移动的特定问题，我的程序使用曼哈顿在约 8 秒内解决了问题，但在相同的情况下使用线性冲突会导致程序无限期运行并挂断我的机器。

我一遍又一遍地检查我的代码，在我的线性冲突或曼哈顿启发式代码中找不到错误。因此，这个一般性问题要确定。

以下实例导致上述问题。

我正在使用 A* 搜索和广度优先搜索来查找 8 谜题中的获胜游戏状态。获胜状态是这样的

并存储为这样的列表

我使用启发式函数对每个节点进行评分（基于其状态），但我相信我对评分最高的节点进行优先排序的方法大大降低了我的程序速度。实际上，我所做的广度优先搜索算法的性能大大优于 A* 算法（尽管大部分内部工作是相同的）。

我相信减慢我的 A* 搜索速度的主要原因是我使用边缘中的位置（包含我的节点的列表）来指示下一个要优先考虑的节点。

所以如你所见，每次将一个节点添加到边缘时，它都会寻找一个得分比它差的节点，然后将自己插入到它的前面。这确保我在执行 fringe.pop(0) 时至少获得得分最高的节点。但是将项目插入一个巨大的列表的中间并不是一个非常快速的动作，是吗？什么是更好的选择？

我还考虑过不对边缘列表进行排序，但这似乎同样糟糕或更糟（因为每次弹出节点时都必须搜索整个列表。

我正在使用 php 制作一个 3x3 的解谜器。零是您可以移动的自由空间。例如：

至

至

我已经制作了随机发生器 - 制作了 50 个随机动作。但我是堆栈，使用求解器算法。

输出应该是解决它的所有步骤。

我已经有了解决一步难题的工作方法，但我不知道如何递归地使用它。

在 8 字谜题中，当它在棋盘中找到空白棋子（用 0 表示）时，它需要获得所有相邻棋子，一步可以到达。

由于我在实现中将二维板映射到一维数组，因此index()在我的代码中使用它确实有意义。

我想不出一种优雅的方式来实现neighbors()现在，因此它现在涉及相当多的冗余代码。

在阅读人工智能一种现代方法时，我遇到了从给定问题的子问题的解决方案成本中推导出启发式的概念。

例如，以下拼图显示了 8 拼图实例的子问题，其中目标是将图块 1、2、3、4 放置到正确位置。

然后，作者扩展了这个概念，说这些从子问题导出的启发式可以通过取最大值来组合。

此外，通过使用这种方法，与曼哈顿距离等简单的启发式方法相比，性能大大提高。

我一直试图围绕复合启发式方法及其推理进行思考。假设我们从以下子问题的解决方案成本中得出两个启发式：

将复合启发式像：

1. 真的在为完整的 8 道难题寻找解决方案吗？

在我看来，使用像h1...8(n)这样的启发式，我们最终会在启发式h1234(n)和h5678(n)之间交替，这反过来可能会导致一个启发式扰乱另一个启发式的工作，并且永远不会达成解决方案。

2. 还是启发式方法会相互帮助以实现完整的解决方案？

老实说，我不明白这怎么可能……

我了解到可以通过遵循某些规则来检查 8 谜题的可解性。 https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

http://ldc.usb.ve/~gpalma/ci2693sd08/puzzleFactible.txt。

我的问题是这种可解性检查是否仅在目标状态（解决方案）处于正确升序时才适用？例子：

现在我的观察是，如果示例中的目标状态是目标状态 2，则可解性检查将起作用。但是如果目标状态是目标状态1，它就行不通了。