我最近一直在用C++開發一個數獨遊戲。我使用SFML製作了一個圖形版本，它工作得很好。然而，我需要實現一個算法來解決數獨，而而不是是一個蠻力算法（所以回溯不適用於我; /）。我已經閱讀了很多方法來解決這個問題，並且我遇到了不同的算法名稱（如Dancing Links），以及僅僅描述搜索如何工作的算法，而沒有提供關於如何實現它的任何特定信息C++。 （即分配一個表或每個單一的「桶」可能的數字列表和搜索解決方案，也有人提到所謂的A *算法？）Sudoku使用C++解決問題
所以這裏是我的問題，什麼樣的算法是公平的易於實現，並且是而不是的回溯之一？哪裏可以找到關於如何在C++中使用它的特定信息？提前致謝。 我的程序在一個二維數組上工作，但我可以以某種方式使桶進入結構，如果需要的話。
Peter Norvig建議使用消除過程（約束傳播），然後搜索。他的文章here提供了一個非常全面的解釋。
在約束傳播您使用以下策略：
(1) If a square has only one possible value, then eliminate that value from the square's peers.
(2) If a unit has only one possible place for a value, then put the value there.
現在，很容易在O（N）時間找到拼圖最初填充的正方形。把他們放在一個隊列中。如果它們的鄰居在傳播約束之後只有一個值，請將其添加到隊列中。重複，直到隊列爲空。
這個難題現在已經解決了，或者沒有進一步的進展可以通過傳播約束。
如果拼圖沒有解決，您可以使用fancier算法，或者像Norvig推薦的那樣使用回溯算法。由於回溯是在拼圖空間的一個典型的小子集上執行的，因此您不使用強力。
那麼它是如何工作的：它將所有可能的不插入任何內容的插入進行分離，然後嘗試插入它們的組合？ –
是的，這是正確的。 – Richard
但是，如何存儲該信息？我應該把所有的桶放入結構中，並創建一個bool數組，告訴我一個數字很好用嗎？還是有更優雅的解決方案？ –
這裏有一個列表：https：//en.wikipedia.org/wiki/Sudoku_solving_algorithms –
你大多需要解決它，就像你做人一樣。 – Jarod42
拋出算法，並找出自己。你可能無法達到最佳結果（儘管你可能會或甚至會改進它們），但你會學到更多。 – Mike