数独 アルゴリズム - ソルバーの仕組みとプログラミング実装
数独ソルバーの実装は、プログラミング学習における優れた題材である。バックトラッキング、制約伝播、ヒューリスティクスの組み合わせにより、任意の数独を瞬時に解くアルゴリズムを解説する。
バックトラッキングの基本
最もシンプルな数独ソルバーは、バックトラッキング (深さ優先探索) で実装できる。空きマスを見つけ、1-9 の数字を順に試し、制約に違反しなければ次の空きマスに進む。違反した場合は前のマスに戻り (バックトラック)、別の数字を試す。このアルゴリズムは必ず解を見つけるが、最悪の場合は全ての組み合わせを試すため非効率である。Easy レベルのパズルでも多くの試行が必要になることがある。
制約伝播による高速化
バックトラッキングの効率を高めるのが制約伝播 (Constraint Propagation) である。数字を配置するたびに、その影響を受ける行 / 列 / ブロックの候補を即座に更新する。候補が 0 になったマスがあれば、その時点でバックトラックする (早期枝刈り)。候補が 1 つになったマスがあれば、自動的に確定させる (ネイキッドシングルの自動適用)。この制約伝播により探索空間が削減され、Peter Norvig が 2006 年に公開した解説では、この消去に「入る場所が 1 つしかない数字を置く」規則を加えるだけで、易しい問題の例がバックトラックなしで解き切れる一方、いつもそうなるとは限らないとしている。
MRV ヒューリスティクス
探索順序の最適化も重要である。MRV (Minimum Remaining Values) ヒューリスティクスは、候補数が最も少ないマスから優先的に探索する戦略である。候補が 2 つのマスは最大 2 回の試行で確定するが、候補が 8 つのマスは最大 8 回の試行が必要になる。MRV により、探索木の分岐が抑えられ、バックトラックが起きにくくなる。同じ解説では、候補の消去と「入る場所が 1 つしかない数字を置く」規則による制約伝播に MRV を組み合わせた Norvig の Python のプログラムが、問題の作者が最も難しいと称した 2 問をそれぞれ 0.01 秒で解いている。
人間の解法との違い
コンピューターのソルバーと人間の解法には本質的な違いがある。コンピューターは全候補を正確に管理し、高速にバックトラックできるため、「推測して試す」アプローチが有効である。一方、人間は推測を避け、論理的に確定できる手順のみで解くことを好む。これは人間のワーキングメモリの制約によると考えられる。バックトラックは複数の状態を記憶する必要があり、人間には負担が大きい。数独の難易度は、人間が推測なしで解けるかどうかを基準に設計されることが多い。
ソルバーが解く速さの正体
厳密被覆問題としての数独
数独は、数学的には厳密被覆問題 (Exact Cover) の一種として定式化できる。各マスに数字を入れるという行為を、満たすべき制約の集合をちょうど一度ずつ覆う選択として表現するのだ。この見方をすると、ドナルド・クヌースが提唱した Dancing Links (DLX) と呼ばれるアルゴリズムを数独に当てはめられる。DLX は、連結リストの要素を一時的に外したり戻したりする操作でバックトラックを高速化する技法で、原論文ではポリオミノの敷き詰めのような組み合わせパズルを対象にしている。同じ問題でも、見方を変えると別の強力な解法が見えてくるのは、計算機科学の面白さの一つだ。
ソルバーの用途と限界
数独ソルバーは、単に答えを出すためだけのものではない。むしろ実用上重要なのは、パズル生成における唯一解の検証や、難易度の推定だ。生成器はソルバーを使って、作ったパズルが本当に一つの解しか持たないかを確かめ、また人間の解法を模したソルバーでどのテクニックが必要かを判定する。一方、解答を表示するためにソルバーを使うのは、パズルの楽しみを奪う本末転倒な使い方になりかねない。ソルバーはあくまで裏方の道具であり、その真価は、遊ぶ人に良質な問題を届けるための検証と分析にこそある。