Java 中的 8 拼图问题

这个谜题包含了其他 8 个谜题的答案。

玩家会得到一个 3x3 的棋盘，上面有 8 个数字块（每个数字块都有 1 到 8 的数字）以及一个空格。利用空格，按照逻辑顺序排列数字块，使其与最终的排列匹配。分配的空间可以容纳四个相邻的数字块（左、右、上和下）。

一个例子是

1. DFS（深度优先搜索）（暴力搜索）

我们可以对这样的状态空间树进行深度优先搜索，它包含了问题的所有可能解，或者从起始状态开始的所有可能状态。

8 拼图的状态空间树

在此解决方案中，后续移动不一定总是使我们更接近目标，反而可能使其更远，无论初始状态如何，对状态空间树的搜索都从根节点开始沿着最左边的路径进行。使用这种方法可能永远找不到答案节点。

2. 可以使用广度优先策略来搜索 BFS（暴力搜索）的整个状态空间树。总是能找到距离根节点最近的目标状态。无论起始状态如何，算法仍然执行与 DFS 完全相同的步骤。

3. 第三，分支定界法 使用一个“智能”的排名函数，有时也称为近似成本函数，可以通过避免搜索不包含答案节点的子树来加速单个答案节点的查找。但它执行的是类似 BFS 的搜索，而不是使用回溯技术。

分支定界法本质上包含三种不同类型的节点。

1. 首次活节点 一个已生成的但尚未产生任何子节点的节点被认为是“活的”。
2. E 节点（扩展节点）此时，正在对活节点 E 的子节点进行研究。或者，E 节点似乎是一个正在扩展的节点。死节点
3. 死节点是一个已生成的节点，它不会被改进或进一步研究。死节点的全部子节点都已被扩展。

成本函数

搜索树的每个节点 X 都附带一个成本。成本函数可用于确定下一个 E 节点。下一个 E 节点具有最低成本。成本函数的定义是

C(X) = g(X) + h(X)，其中

g(X) = 从根节点到当前节点的成本

h(X) = 从 X 到答案节点的成本。

最佳拼图尺寸为 8。基于成本的算法

为了将一个数字块向任何方向移动，我们假设这需要一个单位成本。因此，我们为类似 8 拼图方法之类的算法定义成本函数如下：

c(x) = f(x) + h(x)，其中

f(x) 是路径中从根到 x 的距离（到目前为止的移动次数）

h(x) 是不在正确位置的非空白数字块的数量（错误放置的数字块的数量）。要将状态 x 更改为目标状态，至少需要 h(x) 次移动。

我们有一个算法可以估计 h(x) 的未知值，该算法是可用的。

完整算法

下图显示了通过上述技术从提供的初始配置到最终配置（例如 8 拼图）所采取的路径。您应该意识到，只有成本函数值最低的节点才会被扩展。

程序

文件名：PuzzleProblem.java

输出

0 1 2 
4 5 8 
6 7 3 

0 1 2 
4 5 8 
6 7 3 

0 1 2 
4 7 5 
6 8 3 

0 1 2 
4 7 5 
8 6 3