问题标签 [sliding-tile-puzzle]

我正在研究一个 8-Puzzle Solver - 使用最佳优先搜索 + Hamming 距离（瓷砖不合适）启发式 - 这是我们作为项目所必需的。

我首先在一个单独的 cpp 文件中定义了一个Stat Struct，它在头文件中如下所示：

接下来是 main.cpp 文件：

现在，当我使用这样的示例输入运行程序时：

它解决了难题，一切都很好。但是在我尝试的所有其他输入中，开放集在达到目标之前就变空了，尽管这些难题有解决方案。

编辑： 我试图查看进入开放集的统计数据，但没有，所以我使用下面的输入作为示例，我得到了什么：

打开的统计数据：

解决这个难题需要哪些步骤。

未在 Closed 中找到且未进入 Open 的统计信息：

因此，Open 集表示上述统计信息存在于 Open 中并拒绝输入它们，但 Open 中没有此类统计信息，并且这些状态的启发式值不同 On Open(4,4,5,5,5,5)其他（6,6,5,7）。

有人可以告诉我为什么 Open 拒绝输入这些统计数据，就好像它们已经存在一样。提前致谢。

我正在应用曼哈顿启发式的 A*（和 IDA*）搜索来寻找 15 谜题的解决方案。

利用我不想要问题的最佳解决方案这一事实，由于当前例程太慢，我如何加快搜索速度。

我已经使用 BFS 算法解决了一个 8 难题，并将所需的移动存储到一个数组中，然后将这些数字转换为 0，表示空白空间需要向上移动或向下移动 1 或向左移动 2 或向右移动 3。我不知道如何用 BFS 中的相应动作为 8 个方格设置动画以解决难题。我知道如何使用计时器以及一般如何制作动画，只是不知道如何在正确的时间按顺序制作正确的正方形动画。他们总是需要在任何给定方向上移动 80 个像素。如果有人能指出我正确的方向，我将不胜感激。

我设法用 RNG 蛮力解决了这个问题，即使工作网格是 3x3，也需要大约 4-5 秒才能找到最佳解决方案。

我想知道如何在没有蛮力的情况下生成与蛮力相同的动作。

我将列出 2 个示例和蛮力找到的解决方案。我试图分析解决方案以找出它选择它们的原因，但我什么也想不通。

该游戏通过在两个方向（从左到右）和（从右到左）上使用循环旋转来工作

从左到右循环旋转这样做
If [a, b, c] then [b, c, a]
从右到左循环旋转这样做
If [a, b, c] then [c, a, b]

游戏数据可以这么说（它可以是 1 到 9 的任何排列）
例如
Data = 7, 2, 6, 1, 5, 4, 3, 8, 9

我可以用 8 种不同的方式移动桌子上的棋子。
1）基于行的循环旋转（从左到右）。
2）基于Row的循环旋转（从右到左）。
3) 基于列从上到下。
4) 基于列的自下而上。
现在 5 到 8 不需要 Column 或 Row，因为它们是对角线设置的。
5) 从左上到右下（从左到右）。
6）从左上到右下（从右到左）。
7）从右上到左下（从左到右）。
8) 从右上到左下（从右到左）。

数据加载如下

• 007 | 002 | 006
• 001 | 005 | 004
• 003 | 008 | 009

解决方案蛮力：
1）。[Top-Right] 到 [Bottom-Left]（从右到左）
2）。从下到上，列：0
3)。从左到右，行：1

这是模拟的解决方案

1）。[Top-Right] 到 [Bottom-Left]（从右到左）

• 007 | 002 | 003
• 001 | 006 | 004
• 005 | 008 | 009

2）。从下到上，列：0

• 001 | 002 | 003
• 005 | 006 | 004
• 007 | 008 | 009

3）。从左到右，行：1

• 001 | 002 | 003
• 004 | 005 | 006
• 007 | 008 | 009

这是示例 2，需要 6 步才能解决

• 009 | 008 | 007
• 006 | 005 | 004
• 003 | 002 | 001

解决方法：（6 步）
1）。[Top-Right] 到 [Bottom-Left]（从右到左）
2）。从上到下，列：1
3)。从下到上，列：0
4)。[Top-Left] 到 [Bottom-Right]（从左到右）
5)。从左到右，行：1
6)。从右到左，行：2

所以这是一个非常简单的难题，但找到有效的解决方案并不是一项简单的任务。有人可以指导我正确的方向。

我试图从这个用 BFS 实现的代码开始用 DFS 解决 8 难题。最简单的方法是什么？我研究过的所有代码要么正常工作，要么不完整，这让我比以前更加困惑。

我正在解决 8 谜题。这是一个看起来像这样的问题：

图片由：https ://ece.uwaterloo.ca/~dwharder/aads/Algorithms/N_puzzles/ 提供（您还可以在此处查看 8 拼图的更详细描述）。用户可以将与空白相邻的正方形移动到空白中。任务是恢复如图所示的排列，从一些任意排列开始。

现在，当然可以将状态描述为 9 位的排列。在显示的图片的情况下，排列是：

但是，并非所有排列都可以从所示配置中获得。因此，我有以下问题。

1. 通过将瓷砖滑入空白中，从所示的初始配置中可以获得多少排列？

2. 调用上述 N 的答案。现在，我想要一个从 1 到 N 的整数到排列的 1-1 映射。也就是说，我想要一个接受排列并返回适当整数的函数，以及一个接受整数并返回排列的函数。映射必须是双射（即不完美的散列是不够的）。

I implemented the iterative deepening a-star search(for the 8-Puzzle problem, but can accept other problems) and ran it on an input. It ran unsuccessfully for 2 hrs. For simpler inputs that are close to goal node it works fine. Others have got it to work for this input. I am not sure whether my implementation is just inefficient or goes into an infinite loop

PuzzleSolver.java$ida

PuzzleSolver.java$CheckDup

Start state(failed):

Goal state:

(worked for 1 3 4 8 6 0 7 5 2) I have not included Node.java because I am pretty sure it works after running other search algorithms like best-first, dfs. It is difficult to provide an SCCE, so I am just asking for help spotting any obvious bugs in the ida implementation.

EDIT: Solved issue, but still trying to figure out a termination condition when the goal is not reachable. IDA* does not keep a list of explored nodes, so how can I know if I have covered the whole solution space?

我使用 A* 算法成功地实现了一个 8 谜题求解器，现在我对其进行了改动：谜题中可能有多个空白区域，并且瓷砖上的数字不再是唯一的（可能有是相同的）。

虽然算法在我修改它以生成所有空白空间的后继状态后有效，但它并没有以尽可能少的移动数解决游戏（因为当我试图解决它时，我实际上想出了更少的移动数手，惊喜！）

问题：在这个谜题中，曼哈顿距离仍然是一个可行的启发式方法吗？如果不是，启发式可能是什么？

我正在尝试制作一个可以解决 8puzzle 问题的 Java 程序

解决过程如下：

-首先我创建一个包含初始网格（初始状态）的初始节点

• 我将节点放入队列

• 我测试节点是否是目标，所以我使用堆栈来保存解决方案路径（从节点到初始根）

否则我将在队列中添加他的继任者（代表可能的 0 排列），然后我重做测试。

这是代码：Noued 类

Taquin8 类：

结果是这样的：

我正在通过 Ant Colony Optimization 实现一个 15 谜题求解器，并且我正在考虑一种有效地将每个状态散列成一个数字的方法，因此我浪费的字节数最少。

状态由 16 个数字的列表表示，从 0 到 15（0 是洞）。

像：

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]

所以我想创建一个唯一的数字来识别那个状态。我可以将所有数字转换为以 16 为基数的数字，但我认为这不是很有效有什么想法吗？

谢谢