我的任務是使用迭代廣度優先搜索演算法來解決數獨問題，但我正在努力將這個演算法準確地應用于這個問題。
我發現我需要一個佇列，我必須遍歷這個佇列，直到它不為空。
我有以下演算法來驗證一個值是否適合某個特定的單元格：
- 檢查是否連續不存在此類值。
- 檢查列中是否不存在此類值。
- 檢查塊中是否不存在此類值。
但是當我在某個時候繼續使用這種演算法時，我必須回溯并更改先前選擇的值，因為它可能會被證明是錯誤的。
如何使用 BFS 將回溯應用到這個數獨問題？
uj5u.com熱心網友回復：
BFS 中不需要回溯。相反，BFS 為您提供了許多并行的路徑。如果一條路徑最終導致不一致的網格，它就會死掉。唯一要做的就是對它不做任何事情，即不要像通常所做的那樣將派生自它的下一個狀態推入佇列。
BFS 遍歷本身可以通過多種方式組織，但它可能如下所示：
最初，佇列以原始網格狀態開始。然后重復以下步驟，只要佇列不為空且仍有空閑單元格：
- 從佇列中取出一個網格狀態。
- 取下一個空閑單元格。
- 在不違反您列出的任何規則的情況下，確定此空閑單元格可以獲得哪些值。
- 為其中的每一個創建一個網格狀態，并將它們排入佇列。
當第三個子彈步驟沒有產生可能的值時，分支將“死亡”。在這種情況下，下一步將不會將任何內容排入佇列，這正是您想要發生的事情。錯誤的路徑被消除。回圈仍將繼續并考慮佇列中可能存在的其他替代網格。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446392.html
上一篇：樹遍歷導致串列