这个谜题背后的理论是什么？
What's the theory behind this puzzle?
我最近发现了上面的益智游戏。 objective就是拼成一个大三角形，相邻三角形上的图形部分的形状和颜色相匹配。
解决此问题的一种方法是应用穷举搜索并测试每个可能的组合（大约 7.1e9）。我写了一个简单的脚本来解决它(github)。
由于这个谜题已经很老了，暴力破解这个问题在当时可能是行不通的。那么，解决这个问题的更有效方法（algorithm/mathematical 理论）是什么？
这等同于Edge-matching问题（有一些正多边形），当然是np-complete（我还有更多的负面结果假设近似值）。这意味着，存在很难解决的难题（至少在 P != NP 的情况下）。
一个有趣的side-note：有一个非常流行的（商业）edge-matching拼图叫做Eternity II，它的奖金为两百万美元。据我所知，它仍未被收藏。
这个问题导致了很多尝试和blog-writings，这应该为您提供很多解决这类问题的方法。
失败的（就：没有解决 full-size E2 难题；但其他困难的）方法，应该比 exhaustive-search（没有启发式）更好：
- SAT-solving（我认为最强大的完整方法）
- Constraint-programming
- 通用元启发式算法（调整到某些 problem-statistics 时有很大潜力）
一些有趣的资源：
Complexity-theory: 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-solving 方法：Heule, Marijn JH. "Solving edge-matching problems with satisfiability solvers." SAT (2009): 69-82.
Edge-matching作为基准（因为硬度）：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.
解决此类问题的一种常见方法是 回溯。
您选择一个起点，放下其中一张牌，然后尝试在邻近的地方找到匹配的牌。当你遇到困难时，你备份一个，然后在那里尝试另一种选择。
最终你已经尝试了每一种可能性，而没有为大量的死胡同而烦恼。一旦你卡住了，就没有必要以任何方式填写其余部分，因为你仍然会卡在那个点上。
最近，Knuth 将他的 Dancing Links 算法应用于这种性质的问题，从而获得了更高的效率。
对于您的示例大小的问题，只有 9 个部分和两个 "colors"，所有解决方案最多在几秒钟内就可以找到。
我最近发现了上面的益智游戏。 objective就是拼成一个大三角形，相邻三角形上的图形部分的形状和颜色相匹配。
解决此问题的一种方法是应用穷举搜索并测试每个可能的组合（大约 7.1e9）。我写了一个简单的脚本来解决它(github)。
由于这个谜题已经很老了，暴力破解这个问题在当时可能是行不通的。那么，解决这个问题的更有效方法（algorithm/mathematical 理论）是什么？
这等同于Edge-matching问题（有一些正多边形），当然是np-complete（我还有更多的负面结果假设近似值）。这意味着，存在很难解决的难题（至少在 P != NP 的情况下）。
一个有趣的side-note：有一个非常流行的（商业）edge-matching拼图叫做Eternity II，它的奖金为两百万美元。据我所知，它仍未被收藏。
这个问题导致了很多尝试和blog-writings，这应该为您提供很多解决这类问题的方法。
失败的（就：没有解决 full-size E2 难题；但其他困难的）方法，应该比 exhaustive-search（没有启发式）更好：
- SAT-solving（我认为最强大的完整方法）
- Constraint-programming
- 通用元启发式算法（调整到某些 problem-statistics 时有很大潜力）
一些有趣的资源：
Complexity-theory:
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-solving 方法：
Heule, Marijn JH. "Solving edge-matching problems with satisfiability solvers." SAT (2009): 69-82.Edge-matching作为基准（因为硬度）：
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.
解决此类问题的一种常见方法是 回溯。
您选择一个起点，放下其中一张牌，然后尝试在邻近的地方找到匹配的牌。当你遇到困难时，你备份一个，然后在那里尝试另一种选择。
最终你已经尝试了每一种可能性，而没有为大量的死胡同而烦恼。一旦你卡住了，就没有必要以任何方式填写其余部分，因为你仍然会卡在那个点上。
最近，Knuth 将他的 Dancing Links 算法应用于这种性质的问题，从而获得了更高的效率。
对于您的示例大小的问题，只有 9 个部分和两个 "colors"，所有解决方案最多在几秒钟内就可以找到。