这个难题背后的理论是什么？

Question

我最近遇到了上面的益智游戏。目标是以这样的方式形成大三角形，使得相邻三角形上的图形的部分的形状和颜色匹配。

解决此问题的一种方法是应用详尽的搜索并测试每种可能的组合（大约7.1e9）。我写了一个简单的脚本来解决它（github）。

由于这个难题已经相当陈旧，因此强行解决这个问题可能并不可行。那么，解决这个问题的更有效的方法（算法/数学理论）是什么？

Answer 1

这相当于Edge-matching问题（有一些正多边形），当然是np-complete（并且我假设关于近似值有更多的负面结果）。这意味着，存在很难解决的难题（至少如果P！= NP）。

一个有趣的侧面说明：有一个非常受欢迎的（商业）边缘匹配拼图叫做Eternity II，奖金价值200万美元。据我所知，它仍然不动。

这个问题导致了许多尝试和博客写作，它们应该为你解决这些问题提供很多帮助。

失败（就以下方面而言：没有解决全尺寸的E2难题;但是其他难以解决的问题）方法应该比穷举搜索（没有启发式方法）好得多：

• SAT解决（在我看来最强大的完整方法）
• 约束编程
• 常见的Metaheuristics（调整到一些问题统计时有很多潜力）

一些有趣的资源：

• 复杂性理论：Demaine, Erik D., and Martin L. Demaine. "Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity." Graphs and Combinatorics 23.1 (2007): 195-208.
• 一般硬度分析（实用）：Ansótegui, Carlos, et al. "How Hard is a Commercial Puzzle: the Eternity II Challenge." CCIA. 2008.
• SAT解决方法：Heule, Marijn JH. "Solving edge-matching problems with satisfiability solvers." SAT (2009): 69-82.
• 边缘匹配作为基准（因为硬度）：Ansótegui, Carlos, et al. "Edge matching puzzles as hard sat/csp benchmarks." International Conference on Principles and Practice of Constraint Programming. Springer Berlin Heidelberg, 2008.

Answer 2

解决此类问题的一种常见方法是使用回溯。

你选择一个起始位置，放下一个瓷砖，然后尝试在邻近的地方找到它的匹配。当你遇到困难时，你备份一个，然后在那里尝试替代方案。

最终你已经尝试了所有的可能性，而没有花费大量的死胡同。一旦你陷入困境，以任何方式填补其余部分毫无意义，因为你仍然会被困在那一点上。

最近，Knuth将他的Dancing Links算法应用于这种性质的问题，从而获得了更高的效率。

对于一个问题你的例子的大小，只有9件和两个“颜色”，所有的解决方案最多只能在几秒钟内找到。