问题标签 [sliding-tile-puzzle]

我正在研究一个搜索算法项目，寻找 16 谜题的解决方案。

我有两个包含二维数组的结构列表board[N][N]

列表中的数字在 0-15 范围内是唯一的，不同的是它们的顺序。

如您所见，板之间的唯一区别是数字的顺序。显然，可以遍历每个板检查是否

但是，如果列表中有成百上千个板，则不希望以这种方式比较它们。

有没有办法快速或有效地比较两块板的相同性？

*首先我的英语不好，请试着理解我。我想创建 Slide Puzzle 游戏，但我不了解滑动块的方法和单击滑动事件的方法。（我的意思是 MouseLister）现在我只有 GUI

感谢您的帮助。

我制作了一个类似于 15 谜题的游戏。Node 类存储棋盘状态、它的父节点和它的深度。我在动画解决问题时遇到了麻烦。由于在调用 Thread.sleep 时按下按钮时会调用此方法，所以 gui 会冻结，直到最终节点的状态显示在屏幕上。我怎么能在从一种状态到另一种状态的转换之间延迟一段时间的动画？

我正在尝试在 Prolog 中解决 15 个难题，我需要找到最少的移动次数。

在这里，我们有一个带有详细答案的示例拼图。https://rosettacode.org/wiki/15_puzzle_solver

我正在使用 A* 搜索，使用曼哈顿距离作为启发式。

首先，我确保程序是确定性的。规则要么不适用，要么快速失败，要么在没有回溯的情况下运行完成。为了优化空间，我使用了一个数字来表示状态。搜索队列使用二项式队列进行优化，访问检查使用哈希树进行优化。但是，性能仍然很糟糕。

这是我对二项式队列的实现：

这是我对哈希树的实现：

最后，解谜代码：

按原样，代码在我的计算机上不会在几分钟内运行完成。我做了一个减少目标的配置文件（运行）（例如，当曼哈顿距离为 10 时停止），大部分时间都花在垃圾收集上。

我读过关于 StackOverflow 上的另一个线程谈论同样的事情，“解决方案”是使用约束库，这是我不能使用的东西。

我用尽了我的技巧，坦率地说，我不是一个经常使用 Prolog 的程序员。知道如何在速度方面做得更好吗？

我正在尝试编写一个广度优先搜索程序来解决 8 难题。当我运行以下代码时，出现以下错误：

* `/home/a.out' 中的错误：free()：无效指针：0x0000000001f81430 *
中止

我很确定问题在于this指针的使用以及我如何存储父节点。有什么帮助吗？

现在我只专注于寻找目标。我还没有实现目标路径并打印最终解决方案。

我正在实施广度优先搜索来解决 8 难题。当我尝试使用this指针创建新节点并指向当前节点时，父指针返回垃圾值。这是由于迭代器无效吗？有没有办法绕过这个问题，也许是通过使用与向量不同的容器？

代码：

我正在做 8 拼图挑战，我必须以最短的路径成本以正确的顺序排列图块。对于我的启发式方法，我将错位瓷砖的数量+ n 瓷砖的距离与其目标位置相结合。

目标是

对于这样的谜题

它工作得很好

但是有了这个配置

它无限地选择这个组合作为最短的

1)

2)

然后 1) 然后 2)

有人告诉我，以下 8 个拼图 Solver 的 A* 实现是错误的，谁能告诉我哪里错了以及如何纠正它？

另外：这会在线程“main”中引发异常 java.lang.OutOfMemoryError: Java heap space即使构建进程堆大小设置为 2048。

这是 Solver.java

还有 Board.java，以防万一：

我正在尝试创建具有众所周知的滑动拼图的不同可能状态的树

如果你不知道，它是这样的：

你必须在哪里做到这一点：

基本上，每个状态都会生成新状态，具体取决于如何移动空白空间（向上、向下、向左或向右）

我想要的是创建树，所有状态都将根作为拼图的初始状态，但是当向树添加子（新状态）时，它应该检查该状态是否已经添加到树中的任何位置

你介意帮我实现吗？提前致谢 ：）

这是我当前的代码RecursionError: maximum recursion depth exceeded while calling a Python object

节点类：

树生成方法（认为self是拼图状态）：

我必须使用具有两个启发式的 A* 算法来实现一个 8 谜题求解器。第一个启发式只是不合适的瓦片的总和，第二个是所有瓦片与目标状态的曼哈顿距离之和，我们将其定义为：

我们给出了不同深度的样本测试。我使用第一个启发式的实现通过了所有这些情况，但是第二个启发式在达到 14 深度后没有通过某些测试用例：

（还有更多失败的测试，这些只是前三个）因为当我使用第一个启发式时它似乎适用于所有情况，我猜第二个启发式有问题。这是我的抽象“节点”类：

这是利用第二个启发式的节点类：

任何见解都会有所帮助 - 如果问题不在第二个启发式中，那么我真的会被难住，因为第一个启发式工作完美无缺！