解决平铺/拼图游戏的算法

我一直在考虑解决小难题的算法。我在互联网和 stackoverflow 上发现了不同的算法，但它们在某些方面不能满足我的需求:

我的拼图只有一种颜色，上面没有图像/图案/...

零件的每条边都可以是8个选项之一，与图片上的类似(例如可以将零件描述为ABCD、cdab、cBBb、ADcb)；没有更复杂的结构或类似的东西

我想解的谜题不大，没有比 8x8 大的谜题

角/egde 块没有特定的边缘，结果不会是一个干净的矩形

并非我所有的谜题都能解开

零件可以旋转但不能转动

每个拼图部分都是独一无二的

Example puzzle parts

最佳答案

所以我的起点只是蛮力 - 将片 0 放在 (0,0) 位置，然后开始尝试 (0,1) 中的任何剩余片直到适合，然后移至 (0,2)等。在任何步骤中，如果没有适合该空间的棋子，请取出以前适合的棋子并尝试为该正方形找到新的棋子。

我无法证明这一点，但我怀疑填充块以便您更有可能评估具有 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()。哎呀。

关于解决平铺/拼图游戏的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15121903/