4

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

  • 我的拼图只有一种颜色，上面没有图像/图案/...
  • 零件的每个边缘都可以是 8 个选项之一，类似于图片上的它们（例如，您可以将零件描述为 ABCD、cdab、cBBb、ADcb）；没有更复杂的结构或类似的东西
  • 我要解决的谜题不是很大，没有比 8x8 更大的谜题
  • 角/egde 块没有特定的边缘，结果将不是一个干净的矩形
  • 不是我所有的谜题都是可以解决的
  • 零件可以旋转但不能转动
  • 每个拼图部分都是独一无二的

拼图零件示例

4

1 回答 1

2

所以我的出发点只是蛮力 - 将第 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（）。哎呀。

于 2013-02-27T21:05:06.773 回答