数独 アルゴリズム - ソルバーの仕組みとプログラミング実装

最もシンプルな数独ソルバーは、バックトラッキング (深さ優先探索) で実装できる。空きマスを見つけ、1-9 の数字を順に試し、制約に違反しなければ次の空きマスに進む。違反した場合は前のマスに戻り (バックトラック)、別の数字を試す。このアルゴリズムは必ず解を見つけるが、最悪の場合は全ての組み合わせを試すため非効率である。Easy レベルのパズルでも数千回の試行が必要になることがある。

バックトラッキングの効率を劇的に改善するのが制約伝播 (Constraint Propagation) である。数字を配置するたびに、その影響を受ける行・列・ブロックの候補を即座に更新する。候補が 0 になったマスがあれば、その時点でバックトラックする (早期枝刈り)。候補が 1 つになったマスがあれば、自動的に確定させる (ネイキッドシングルの自動適用)。この制約伝播により、探索空間が大幅に削減され、ほとんどのパズルがバックトラックなしで解ける。

探索順序の最適化も重要である。MRV (Minimum Remaining Values) ヒューリスティクスは、候補数が最も少ないマスから優先的に探索する戦略である。候補が 2 つのマスは最大 2 回の試行で確定するが、候補が 8 つのマスは最大 8 回の試行が必要になる。MRV により、探索木の分岐が最小化され、バックトラックの発生頻度が大幅に減少する。制約伝播と MRV の組み合わせにより、世界最難のパズルでも 1 ミリ秒以内に解ける。