這個難題背後的理論是什麼？

Question

我最近遇到了上面的益智遊戲。其目標是形成一個大三角形，以便相鄰三角形上的圖形部分的形狀和顏色相匹配。

解決此問題的一種方法是應用詳盡搜索並測試每種可能的組合（大約7.1e9）。我寫了一個簡單的腳本來解決它（github）。

由於這個難題是相當古老的，蠻力這個問題可能不是當時可行的。那麼，解決這個問題的更有效的方法是什麼（算法/數學理論）？

Answer 1

這相當於Edge-matching問題（有一些規則多邊形），這當然是NP完全（也有我承擔約近似更負的結果）。這意味着，存在難以解決的難題（至少如果P！= NP）。

一個有趣的側面說明：有一個非常受歡迎的（商業）邊緣匹配益智Eternity II，其獎金值爲200萬美元。據我所知，這仍然是不合理的。

這個問題導致了許多嘗試和博客寫作，這應該爲您解決這些問題提供很多幫助。

失敗（在以下方面：沒有解決全尺寸E2的難題;但其他硬的）方法，這應該工作比窮舉搜索好得多（不含啓發式）是：

• 衛星 - 解決（在我看來最強大的完整方法）
• 約束編程（調諧至一些問題的統計數據有很大的潛力）
• 常見的超啓發式

個

一些有趣的資源：

• 複雜性理論：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件和兩個「顏色」，所有解決方案將在幾秒鐘內發現最多。