我一直在考虑解决小谜题的算法。我在 Internet 和 stackoverflow 上找到了不同的算法，但它们在某些方面不能满足我的需求:
- 我的拼图只有一种颜色，上面没有图像/图案/...
- 零件的每条边可以是8个选项中的一个，与图片上的相似(例如您可以将零件描述为ABCD，cdab，cBBb，ADcb)；没有更复杂的结构或类似的东西
- 我想解的谜题不大，没有比 8x8 大的了
- 角/边 block 没有特定的边缘，结果不会是一个干净的矩形
- 并非我所有的谜题都可以解决
- 零件可以旋转但不能转动
- 每个拼图部分都是独一无二的
最佳答案
所以我的起点只是蛮力——将棋子 0 放在 (0,0) 位置，然后开始尝试 (0,1) 中的任何剩余棋子直到一个适合，然后继续 (0 ,2), 等等。在任何一步，如果没有适合该空间的棋子，请取出之前适合的棋子并尝试为该方 block 找到新的棋子。
我无法证明这一点，但我怀疑填充碎片会使您更有可能评估具有 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/