algorithm - 解决拼图游戏的有效算法是什么？

Question

昨天我刚刚在玩拼图游戏，不知何故想知道解决它的算法是什么。

作为人类，我遵循的步骤是:

1. 将所有零件分成 3 部分，单平边、双平边和完全没有边。
2. 将平面边缘部分分开，因为它们将成为图像的角
3. 分离单个边 block ，因为它们将形成图像的 4 个端边
4. 最后，没有边缘的部分将形成图像的内部。
5. 匹配颜色和图像 block 以将 block 组合在一起。

我想知道什么是有效解决这个难题的有效算法以及什么数据结构可以提供最佳有效解决方案。

谢谢。

Answer 1

解决此类问题可能看似复杂，尤其是在对难题的大小和复杂性没有限制的情况下。

以下是我对编写解决此类难题的程序的想法。

有四个关键信息，您可以单独或一起用作解决拼图游戏的线索:

1. 每个部分的形状信息(它们的边缘如何出现)
2. 每 block 的颜色信息(相邻的 block 一般会有平滑的过渡)
3. 每件的方向信息(平边和角边可能位于的位置)
4. 整体尺寸和拼图 block 数提供了拼图的大致尺寸

那么程序将提供什么样的信息 - 让我们假设每个拼图 block 都是一个带有透明度信息的小矩形图像，用于识别表示非矩形边缘的拼图 block 部分。

由此，识别四个角 block 相对容易(在典型的拼图中)。这些将恰好有两条具有平坦轮廓的边缘(见下面的等高线图)。

接下来，我将构建有关拼图 block 四个边的形状的信息。此信息可用于构建 adjacency matrix指示哪些部分可以组合在一起。

现在我们可以修剪这个邻接矩阵，以识别那些在相邻配置中具有平滑颜色过渡的部分。这有点棘手，因为它需要一定程度的模糊匹配 - 因为并非每个像素到像素的边界都必然具有平滑的颜色过渡。

使用最初确定的四个角 block ，我们现在应该能够重建拼图中所有 block 的尺寸和位置。

表示边缘形状的一种方便的数据结构可能是等值线图 - 本质上是一组整数，表示从图像的相对侧到图像的四个边中的每一个中的最后一个非透明像素的距离增量一 block 拼图。匹配的片段应该有镜像等高线图。