问题标签 [sliding-tile-puzzle]

目前正在使用 A* 算法解决 8 谜题。作业要求我们使用曼哈顿优先级的 A* 算法来解决这个难题。但是我可以在两个可能的相邻板之间存在联系的特殊情况下（见下文），我该如何进行？

从...开始

{{2,3,5}, {1,0,4}, {7,8,6}}

最终我们归结为在这两者之间进行选择：

如果我们选择使用汉明距离来打破平局，则将选择第二个选择并且不会引导我们找到解决方案，但我们怎么知道我们应该选择第一个板？

所以我试图找到8块拼图中空白块滑动的方向，

我正在使用 X/Y 来确定瓷砖。

这是我的代码。

我遇到的问题是，当调用 mandist 谓词时，它并没有给我我希望的结果。

我确定问题出在 if 语句上，我写了一些伪代码，所以你可以理解我在做什么，

例子：

这然后调用 mandist 谓词

将 D 设置为 1，因此它确保其合法移动

这是意想不到的结果：

我也期待它说Direction = right，因为位置 1/1 是 3x3 网格的最左下角，从左下角开始的唯一移动是向上或向右

1/3 2/3 3/3

1/2 2/2 3/2

1/1 2/1 3/1

我正在尝试使用具有 3 个不同启发式函数的 A* 算法来解决 N 难题。我想知道如何在时间复杂度方面比较每种启发式方法。我正在使用的启发式方法是：曼哈顿距离、曼哈顿距离 + 线性冲突、N-max 交换。特别是对于 8 拼图和 15 拼图。

所以我对Java有点陌生，并决定创建某种滑动数字谜题。这是我所拥有的：

1 应该是空白点，但我稍后会弄清楚。我的问题是代码打印：

当我想要它打印时：

我也尝试过做一个嵌套循环，因为它太可怕了，我不好意思在这里展示它。我会尝试使用二维数组吗？

I need help with fixing my movement code. I am not so javascript friendly. I am just using the old fashion table technique and javascript. I cannot use any jquery or other sources. Here is the code:

我正在尝试实现8-puzzle的求解器。拼图板表示为一个列表。例如，目标状态：

表示为[1,2,3,4,5,6,7,8,0]，其中0表示空白空间。

我已经实现move(+Board,-Move)了成功，Move因为董事会的所有可能状态都远离Board. 此外，我已经实施solvable(+Board)了true是否false可以解决董事会的问题。

我还实现了两个启发式方法manhattan(+Board,+Goal,-H)和hamming(+Board,+Goal,-H)，它计算从Board到的启发式方法成本Goal。例如：

我想将solve(+Board,+Heuristic,-Solution)其作为使用给定Solution解决方案的一种最佳解决方案来实现，并且它必须以精确的一种解决方案确定性地终止。例如：BoardHeuristic

我写了 A* 算法的伪代码：

其中G(Board)是 的实际成本Board，定义为Board从初始板到最佳路径的长度。F(Board)是 的组合成本Board，定义为 的总和G(Board)和估计的成本Board（由启发式函数定义）。当然Closed和Open是由 A* 算法维护的两个集合，Closed包含已访问Open的板，包含未访问的板。

问题是我不知道如何在 Prolog 中执行此操作。我认为维护这两个列表需要一些堆数据结构，但不知道是什么或如何。任何帮助都会很棒。

我已经为一个 8 益智游戏实现了 dfs 搜索，但由于某种原因，我无法让它正常工作，我的堆栈不断为我的 8 益智游戏添加和添加可能的动作，但它永远不会减少答案，我不知道这是否正常，但这是我的代码，以防有人可以帮助我。

我知道代码没有完全优化，我只是想知道为什么它不能像 dfs 那样工作，谢谢。

我必须在 python 中使用 bfs、dfs 和 A* 算法做一个 8 谜题解析器，但我有一些问题。我无法通过所有测试。任何人都可以帮助我吗？

编辑：我编辑了使用一维数组的代码。它适用于：

但python driver_3.py bfs 6,1,8,4,0,2,7,3,5似乎没有找到解决方案。它运行了几分钟而没有找到解决方案。

这是我的代码：

driver_3.py

八拼图.py

节点.py

图.py

前沿.py

我是 Objective-C 的新手，所以我试图通过实现算法来学习。我正在做一个 A* 搜索来解决 8-puzzle 问题。在运行算法本身之前，我想检查给定的拼图组合是否可解。我以前用 C++ 和 Swift 编写过这段代码，但对我来说，它在 Objective-C 中不能正常工作。对于这个数组，它给出的反转计数为 7，而它应该为 0。也许我应该使用 [NSArray objectAtIndex:] 方法来访问元素，然后将它们转换为整数进行比较？我已经测试了不同的方法，并且比较有效。请帮助我找到错误。

目前正在学习A*搜索算法并使用它来找到最快的解决方案N-Puzzle。对于初始起始状态的一些随机种子，谜题可能无法解决，这将导致非常长的等待时间，直到算法搜索整个搜索空间并确定给定起始状态没有解决方案。

我想知道是否有一种方法可以预先计算A*算法是否无法避免这种情况。我已经阅读了一些关于它是如何可能的，但找不到关于如何做到这一点的直接答案。

任何指导或选项表示赞赏。