java - 我怎样才能用计算机程序解决 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

这些 block 可以互锁成两层，每层 5 个，顶层与底层成 90 度角，如上面的链接所示。

我已经使用 Java 为这个问题创建了自己的解决方案，但我觉得这是一个笨拙的解决方案，我有兴趣看到一些更复杂的解决方案。请随意建议通用方法或以您选择的语言提供工作程序。

我的方法是使用上面的数字符号来创建一个“日志”数组。然后，我使用组合/排列生成器尝试日志的所有可能排列，直到找到所有交叉点都等于零的解决方案(即 Peg 到 Hole、Hole 到 Peg 或 Blank 到 Blank)。我使用一些加速来检测给定排列的第一个失败交叉点，并继续进行下一个排列。

我希望你和我一样觉得这很有趣。

谢谢，克雷格。

Answer 1

这个问题似乎是 Boolean satisfiability problem 的一种形式.如果是，最著名的方法就是蛮力。

但是问题的某些对称性和某些属性可以让您减少需要尝试的解决方案的数量。比如——

• 如果你把日志分成两部分5 件套子集 TOP 和 BOTTOM，#TOP 中的 Hook 需要匹配#BOTTOM 中的孔，以及 # 中的孔TOP 需要匹配中的 # pegsBOTTOM，以及 TOP 中的 # flats 需要以匹配 BOTTOM 中的 # flats。如果# 个钉子和 # 个孔匹配，然后# flats 也会匹配，所以你应该不需要检查 # 公寓。
• 有 10 * 9 * 8 * 7 * 6 种方式可以将日志分成两部分5 件套子集。 (一旦你有为子集选择了前 5 个日志TOP，其余日志在子集底部。
• 当您测试 5 block 子集时，有 5 * 8 * 6 * 4 * 2 种方式可以安排一层日志。也就是你pick log 1之后，还剩下4个log。对于第二个日志，你可以从四个中选择，并且有它可以通过两种方式进行定向关于第一个日志。
• 一旦有了基础层，您就可以尝试一次将另一层的每根原木装入其中，直到找到不适合的原木为止。那时，您放弃当前的基础层日志安排并尝试下一个。