Sudoku C++で解決する

Question

私は最近、C++のsudokuゲームに取り組んでいます。私はSFMLを使ってそれのグラフィックバージョンを作ったし、うまく動作します。しかし、ではなく、はブルートフォースアルゴリズムであるので、私は、スードクを解くアルゴリズムを実装する必要があります（バックトラックは私にとってはうまくいかない/）。私はそれを解決するための多くの方法について読んできました。異なるアルゴリズム名（Dancing Linksなど）と、アルゴリズムの実装方法についての特定の情報を与えずに検索の仕組みを記述するアルゴリズムC++。 （つまり、テーブルや個々の "バケツ"に可能な数字のリストを割り当て、解決策を探して、誰かがいわゆるA *アルゴリズムとも呼ばれていますか？）

ここで私の質問は、どのようなアルゴリズムがかなりです実装が簡単でではないバックトラックのものは？そして、C++でどのように使用するかについての情報の特定の部分はどこにありますか？前もって感謝します。 私のプログラムは2次元配列で動作しますが、必要に応じて何らかの形でバケットを構造体にすることができます。

Answer 1

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）時間にパズルで最初に満たされた正方形を見つけるのは簡単です：

は制約伝播では、次の戦略を使用します。それらをすべて待ち行列に入れてください。隣人が制約を伝播した後に単一の値しか持たない場合は、それをキューに追加します。キューが空になるまで繰り返します。

パズルが解決されました。または、制約を伝播することでさらなる進歩ができなくなりました。

パズルが解決されない場合は、ファンディアアルゴリズムを使用するか、Norvigの推奨どおりにバックトラックを使用することができます。バックトラックはパズルスペースの一般的に小さいサブセットで実行されているので、あなたはブルートフォースを使用していません。