数独ソルバー

数独の数字は記号として扱い、計算には使わない。空きマスでは 1..9 から同じ行、列、3×3 ブロックにある数字を除く。候補を一つ置いて再帰し、残りが解けなければそのマスを 0 に戻す。

この取り消しはアルゴリズムの一部だ。候補は現在の盤面から求める。失敗した数字を残すと、次の分岐に存在しない制約を持ち込んでしまう。

MRV で次のマスを選ぶ

最初の空きマスを選ぶ方法でも正しく解ける。最小残余値（MRV）は全ての空きマスを調べ、候補が最も少ないマスを選ぶ。同数なら行優先順で選び、数字は昇順に試す。どちらの戦略も実行順は一定になる。

MRV は矛盾を早く見つけるための規則だ。候補が一つなら選択の余地がなく、ゼロならその分岐は失敗する。六つより二つの候補を先に扱えば、誤った選択の近くで矛盾を見つけやすい。既定の同じ盤面で、選択部分だけを変えると次の結果になる。

後者も同じ解に到達するが、仮置きと取り消しがそれぞれ 53 回増える。この入力で探索木が小さくなることが、MRV の効果を示している。

候補関数は行、列、ブロックにある非ゼロの数字を used 集合へ集め、1..9 との差を求める。選択中は各空きマスの候補数を表示するので、最小値を盤面で確認できる。最初の空きマスを選ぶ場合も、その戦略が見送った候補数の少ないマスは表示される。

一つのヒントが探索を変える

次のプリセットは MRV のコードを固定し、一つのヒントだけを変える。

正しい 7 を固定すると、MRV の軌跡で唯一候補が二つある選択が消え、残りは全て一意に決まる。

4 を固定しても数字の重複は起きない。局所的には合法だが、完成形には拡張できない。二回仮置きすると、候補がゼロのマスに到達する。探索は二回の書き込みを戻し、変更できないヒントまで戻って解なしと判断する。入力盤面も元に戻る。局所的な合法性は、解の存在を保証しない。

盤面が小さく、制約の検査が安価で、一つの解があればよい場合に直接的なバックトラックは向いている。難問を大量に処理するなら、行、列、ブロックのビットマスクを維持して集合の作り直しを減らせる。制約が増える場合や全解探索には、完全被覆、SAT、制約プログラミングも選択肢になる。

数独のバックトラックの仕組み

戦略が (row, col) を選んだ後は、次の契約に従う。

1. 空きマスがなければ true を返す。
2. 選んだマスの候補がなければ false を返す。
3. 候補を一つ置き、その盤面で再帰する。
4. 子呼び出しが成功したら、完成した盤面を保って true を返す。
5. 失敗したらマスを 0 に戻し、次の候補を試す。
6. 全候補が失敗したら false を返す。

ループ不変条件は、候補を試す直前の盤面が、この呼び出しの入口と一致することだ。深い呼び出しが自分の書き込みを戻し、現在の呼び出しも自分の書き込みを戻す。次の候補に失敗した部分木の状態を残さない。

最初の解が見つかれば停止する。解の数は数えず、一意性も証明しない。

数独を解くステップ

既定の盤面には 38 個のヒントと 43 個の空きマスがある。MRV は候補 [4, 7] の (0, 4) を最初に選ぶ。

1. (0, 4) に 4 を仮置きする。
2. MRV により (2, 4) は 7、続く (2, 3) は 3 に決まる。
3. (2, 8) では行、列、ブロックが九つの数字を全て禁止し、子呼び出しが false を返す。
4. (2, 3) の 3 を消す。他の候補がないので、この呼び出しも false を返す。
5. (2, 4) の 7 を消す。この呼び出しにも別の候補はない。
6. 根の呼び出しが (0, 4) の 4 を消す。候補欄には試行済みの 4 x と、未試行の 7 が残る。
7. 根で 7 を試す。以後の MRV の選択は全て強制され、盤面が完成する。

アルゴリズムは 46 回配置し、3 回取り消し、深さ 43 に達する。プレイヤーは 33 の場面を表示する。失敗した分岐と三回の取り消しは一操作ずつ示し、既に説明した候補一つの配置 41 回は、七つの早送りチェックポイントにまとめる。これは説明の進行であり、コードが一括処理するわけではない。盤面とカウンターは一操作ずつの再帰トレースから取得する。

完成した盤面：

5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

その後、全ての行、列、ブロックを三つの検証場面で確認する。各場面は静止しており、一時停止できる。検証用の図形だけを緑にし、数字は通常色に保つことで、確認対象の制約を示す。

時間計算量と空間計算量

空きマス数を B とする。一マスにつき最大九つの候補があるため、大まかな最悪時間の上界は O(9^B) となる。制約と MRV は探索木を縮める。既定例では配置が 99 回から 46 回になるが、最悪時の指数的な上界は変わらない。

この実装は再帰ごとに空きマスを走査し、候補を再計算する。固定の 9×9 盤面では行、列、ブロックの検査量に定数の上限がある。再帰スタックと仮置きの経路は最大 B 個の選択を保持するため、盤面を除く補助空間は O(B)。

MRV が変えるのは探索順であり、正しさではない。候補規則が同じなら、最初の空きマスを選ぶ方法も同じ解集合を持つ。ただし、失敗する分岐を多く探索することがある。

境界ケース

• 完成済みの合法な盤面は、最初の呼び出しで配置せずに true を返す。
• 埋まったマスが局所的に合法でも、候補ゼロの空きマスがあれば矛盾する。
• 複数解がある場合、固定の探索順で最初に見つかった解だけを返す。一意性は確認しない。
• ヒントの重複は探索契約の対象外で、再帰の前に拒否する。本レッスンは全プリセットを事前検証する。
• 解なしプリセットは重複を含まないが完成できない。全ての仮置きを戻した後、None または null を返す。

よくある間違い

• board[row][col] = 0 を省く。 失敗した数字が、本来合法な候補を禁止する。
• 候補ゼロを完成とみなす。 候補ゼロは矛盾であり、空きマスゼロが完成を意味する。
• 最初の候補の失敗で false を返す。 他の候補が残っている可能性がある。失敗の返却はループの後に置く。
• 行と列しか検査しない。 3×3 ブロックの制約を省くと、数独の解ではないラテン方格を作ることがある。
• ヒントを書き換える。 仮置きと取り消しの対象は、入力時に空いていたマスだけ。
• MRV を正しさの必須条件と考える。 最初の空きマスを使っても正しく解ける。既定盤面では探索量が増える。