Sudoku Flowコンピューターは数独をどう解くのか
更新日：2026-10-05
バックトラッキング
ソルバーは空きマスにルール上入れられる数字を試し、そのまま進みます。どの数字を選んでも解にたどり着けない場合は、以前の選択を取り消して別の数字を試します。入れられる数字が最も少ないマスを先に選ぶと、探索を大幅に短縮できることがよくあります。
出典: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
完全被覆とDancing Links
数独は完全被覆問題として表し直せます。各マスと、各行・列・ブロックの各数字が、それぞれちょうど1回ずつ満たされるように数字の配置を選びます。クヌースは2000年11月の論文で、バックトラッキングを用いる自身のAlgorithm Xを効率よく実行する方法であるDancing Linksを説明しました。これを数独の完全被覆モデルに適用すると、問題のすべての解を素早く見つけられます。
出典: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
ランダム探索
一部のプログラムは盤面をランダムに埋めてから、焼きなまし法や遺伝的アルゴリズムなどの手法で数字を入れ替え、ルールに反する箇所を減らします。これらは別のアプローチとして研究されてきました。どれほどうまく機能するかは、プログラムと問題によって異なります。
出典: Wikipedia: Sudoku solving algorithms
人間のように考えるソルバー
ヒントエンジンの役割は異なります。答えを見つけるだけでなく、人がたどれる次の手順を示します。本アプリのエンジンは、ヒドゥンシングルなどの最も簡単なものから、チェーンやほぼロックされた集合（ALS）などの最も難しいものまで、人間が使うテクニックを決まった順序で試し、数字の確定につながる最初のテクニックを使います。難しいテクニックでは、まず候補を除外します。その問題で使った最も難しいテクニックによって、アプリ内での問題のレベルが決まります。
