我一直在思考一个解决小拼图的算法。我在互联网和stackoverflow上找到了不同的算法，但它们在某些方面不符合我的需求：
- 我的拼图块只有一种颜色，没有图像/图案/...
- 每个部分的边缘可以是8个选项之一，类似于图片上的边缘（例如，您可以将部件描述为ABCD、cdab、cBBb、ADcb）；没有更复杂的结构或其他任何东西
- 我想要解决的拼图不大，没有超过8x8的
- 角落/边缘块没有特定的边缘，结果将不是一个干净的矩形
- 并非所有的拼图都能够被解决
- 部件可以旋转但不能翻转
- 每个拼图部件都是唯一的
解决拼图/拼贴谜题的算法
4
- Georg Jung
2
看起来你可能也有多种解决方案？另外，你所说的旋转但未翻转，是指翻转吗？ - Mikeb
是的，可能有多个解决方案。零件不能倒置。它们可以旋转，但形象上只是在一侧绘制的。 - Georg Jung
1个回答
2
因此，我的起点只是用 brute force 方法 - 将第 0 个方块放在 (0,0) 的位置上，然后开始尝试在 (0,1) 中的余下方块中任意一个适合的方块，然后继续移动到 (0,2) 等等。在任何一步中，如果没有适合的方块，则取出之前适合的方块并尝试为该正方形找到一个新的适合方块。
我无法证明它，但我怀疑填充方块以使您更有可能评估具有 2 个约束条件的方块（也就是说，不是做较大的正方形，而是 2x2、3x3、4x4，向外扩展）将比仅做行更快地终止。
它让我想起那些带有动物头和尾的方形块的 3x3 拼图。其中的一个优化是计算配对之间的不匹配 - 如果您拥有比
（编辑）思考后，我认为计数的第一件事就是如果不存在解决方案，则提前退出。NxN 网格有
（编辑 2）在我的代码中，abs() 是我想要使用 min()，失误了。
我无法证明它，但我怀疑填充方块以使您更有可能评估具有 2 个约束条件的方块（也就是说，不是做较大的正方形，而是 2x2、3x3、4x4，向外扩展）将比仅做行更快地终止。
它让我想起那些带有动物头和尾的方形块的 3x3 拼图。其中的一个优化是计算配对之间的不匹配 - 如果您拥有比
a 更多的 A，则您知道 A 倾向于位于拼图的边缘，但是在一个 8x8 的拼图中，你有更少的边缘到内部的比率，因此这种差异不太可能有用，也没有一个好的方法将其集成到算法中。（编辑）思考后，我认为计数的第一件事就是如果不存在解决方案，则提前退出。NxN 网格有
2*N*(N-1) 个内部匹配必须满足。 如果 min(A,a) + min(B,b) + min(C,c) + min(D,d) < 2*N*(N-1)，则知道没有解决方案。（编辑 2）在我的代码中，abs() 是我想要使用 min()，失误了。
- Mikeb
6
抱歉，我不确定怎样计算
|A-a| + |B-b| + |C-c| + |D-d|。它不需要是 NxN 的，也可以是 NxM 的。 - Georg Jung1抱歉，应该详细说明一下 - 在那种情况下，A是指出现在拼图集合中的所有A nubs的总数，a是指出现在拼图集合中的所有
a nubs的总数。取差的绝对值可以得到可以形成的最大数量的A-a匹配。如果没有足够的匹配来填充拼图，则无法解决问题；请注意，反之则不一定成立，即使有足够的匹配，如果它们不能正确排列，仍然可能没有解决方案。 - Mikeb我找不到我的错误 - 我认为应该是
< 4N 或 < 2N+2M。我的错误在哪里？ - Georg Jung14N或2N+2M将是边的数量；该总和设置了匹配条件数量的上限。如果此上限小于所需匹配数，则无法正常工作。在
NxM矩阵中的内部约束数量将为(N * (M-1)) + (M * (N-1))。 - Mikeb我认为
A是一种特定类型的突起，而a则是配合的孔（或相反）？那么我将计算所有不适合任何孔的突起，并将其与边缘突起/孔的数量进行比较？也许我误解了“在这种情况下，A是出现在零件集中的所有A突起的总数，a是所有a突起的总数。”？如何确定“出现在集合中的总数[...]”以及仅“总数”？ - Georg Jung啊，不，我想你是对的，我犯了一个错误。我的大脑很累了。你说的是正确的，|A-a|将是无法使用的数字的数量。我已经更正了我之前回答中的编辑。 - Mikeb
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接