哪些算法我需要學習編寫縱橫文字編織器？

Question

我喜歡學習一些關於算法的知識，特別是可以幫助我構建縱橫文字編織器的算法（簡單的一種）
哪些算法應該學習？

Answer 1

我將與以下幾點入手：

1. Dictionary Data Structures。
2. Strings。
3. Planning。
4. A star search。

開始很小，用一個100字的單詞列表和一個2乘2的填字遊戲。

Answer 2

嘗試使用與DFS類似的回溯功能。所以學習DFS然後學習回溯。

A *也很好，但你需要很好的啓發式。具有A *搜索的前綴樹可能有效。但首先開始簡單的回溯版本。

順便學習回溯的一個優點是，可以解決很多其他的拼圖也使用它，喜歡數獨，15個王后，速度在迷宮和鋸齒鋸拼圖:)

Answer 3

• 有無你決定使用哪種編程語言？在處理字符和字符串時，某些語言比其他語言更好，例如Java和C++具有相當好的字符/字符串處理能力。除了Yuval和Atul提到的之外，我想你需要了解一下Longest Common Substring算法。

• 另請查看this SO thread的解答。有一些算法步驟被討論來創建一個縱橫字謎編織器。你應該有一個有效的算法來實現你遵循的每一步。

Answer 4

你的問題的主要類別是CSP（約束滿足問題），這主要是由回溯算法