什么是解决Jigshaw拼图的有效算法？

Question

昨天我只是玩Jigshaw Puzzle而不知何故想知道解决它的算法是什么.

作为人类,我遵循的步骤:

1. 将所有部件分成3个部分,单个平边,双平边,完全没有边缘.
2. 将扁平的边缘碎片分开,因为它们是图像的角落
3. 将单个边缘片分开,因为它们将形成图像的4个末端边缘
4. 最后,没有边缘的碎片将形成图像的内部.
5. 匹配颜色和图像片段将片段放在一起.

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

谢谢.

Answer 1

解决这样的问题可能看似复杂,特别是如果没有对谜题的大小和复杂性施加约束.

这是我对编写程序来解决这样一个难题的方法的想法.

有四个关键信息可以单独使用,也可以作为解决拼图游戏的线索:

1. 每件的形状信息(边缘如何显示)
2. 每个部件的颜色信息(相邻部件通常具有平滑过渡)
3. 每件的方向信息(平面和角边可能位于其中)
4. 整体尺寸和件数提供了拼图的一般尺寸

那么程序将提供什么样的信息 - 让我们假设每个拼图是一个小的矩形图像,其透明度信息用于识别拼图块中代表非矩形边缘的部分.

由此,识别四个角件(在典型的拼图中)相对容易.这些将具有两个具有平面轮廓的边缘(参见下面的等高线图).

接下来,我将构建有关拼图块四个边缘每个形状的信息.该信息可用于构建指示哪些部分组合在一起的邻接矩阵.

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

使用最初识别的四个角落片段,我们现在应该能够重建拼图中所有片段的尺寸和位置.

用于表示边缘形状的方便的数据结构可以是轮廓图 - 基本上是一组整数,表示从图像的相对侧到拼图块的四个侧面中的每一个中的最后一个非透明像素的距离的增量增量.匹配的碎片应具有镜像轮廓图.