如何用计算机程序解决Log Pile木制拼图？

Question

谁能建议如何使用计算机程序解决Log Pile木制拼图？

请参阅此处以查看拼图:http://www.puzzlethis.co.uk/products/madcow/the_log_pile.htm

图片只显示了一些部分.全套10件配置如下,其中1代表一个钉,-1代表一个孔,0代表一个钉和一个孔.
-1,1,0,-1,0
1,0,1,0,0
1,-1,1,0,0
-1,
-1,0,0 ,-1 -1,1,0,1 ,0
0,1,0,0,1
1,0,-1,0,-1
0,-1,0,1,0
0,0,-1,1,-1
1,0,-1, 0,0

这些部件可以互锁成两层,每层5件,顶层与底层成90度,如上面的链接所示.

我已经使用Java自己创建了这个问题的解决方案,但我觉得这是一个笨拙的解决方案,我有兴趣看到一些更复杂的解决方案.您可以随意提出一般方法或以您选择的语言提供工作计划.

我的方法是使用上面的数字表示法来创建一个"日志"数组.然后我使用组合/置换生成器来尝试所有可能的Logs排列,直到找到所有交叉点等于零的解(即Peg to Hole,Hole to Peg或Blank to Blank).我使用了一些加速来检测给定排列的第一个失败的交叉点并继续下一个排列.

我希望你发现这和我一样有趣.

谢谢,克雷格.

Answer 1

这个问题似乎是布尔可满足性问题的一种形式.如果是,最着名的方法是蛮力.

但是有一些对称性,问题的一些属性可以让你减少你需要尝试的解决方案的数量.例如 -

• 如果将日志分成两个5件式子集TOP和BOTTOM,TOP中的#pegs需要匹配BOTTOM中的#个洞,TOP中的#个洞需要匹配BOTTOM中的#个pegs,以及TOP中的#个字符串需要匹配BOTTOM中的#flats.如果#pegs和#holes匹配,那么#flats也会匹配,所以你不需要检查#flats.
• 有10*9*8*7*6种方法可以将日志分成两个5件式子集.(一旦为子集TOP选择了前5个日志,剩余的日志就在子集BOTTOM中.
• 当您测试5件式子集时,可以使用5*8*6*4*2方式排列一层日志.也就是说,在您选择日志1之后,剩余4个日志.对于第二个日志,您可以从四个日志中选择,并且有两种方法可以针对第一个日志进行定向.
• 一旦有了基础层,就可以尝试一次一个地填充另一个层中的每个日志,直到找到一个不适合的日志.此时,您放弃当前的基础层日志安排并尝试下一个.

Answer 2

根据 Jay Elston 的建议，我将使用以下伪代码来实现它：

 Read in the pieces
 Annotate each piece with its number of pegs and holes
 Generate all possible base layers (10 over 5 = 252, selecting 5 from the set), 
   so that sum(above, pegs) == sum(below, holes) and sum(below, pegs) == sum(above, holes)
   For each base layer, (5! = 120 of them, permuting the 'below' pieces)
      compute 'rotated pieces' for the base layer
      if one-to-one match between top layer and rotated base-layer pieces, 
          report successful solution

对于给定的基层，“旋转件”是您需要覆盖它的理想件。通过计算这些片段并将它们与顶层片段匹配，您可以使用 O(N log N) 排序将旋转片段与真实顶层进行匹配，而不是与所有 N 进行匹配！可能的顶层安排。另外，在第一次不匹配时，您可以提前退出。

编写高效算法的关键是尽早修剪搜索并利用任何对称性。例如，如果您认为拼图是对称的，则可以将运行时间减少一半，因此您可以任意将一块分配到底层：这样您将只有 4 个基础层中的 9 个需要探索。