バックトラッキング

ばっくとらっきんぐ

試行錯誤により解を探索するアルゴリズム。行き詰まったら前の状態に戻り別の選択肢を試す。

バックトラッキング (Backtracking) は、深さ優先探索に基づく問題解決アルゴリズムである。数独ソルバーでは、空きマスに数字を仮置きし、制約違反が発生したら前の状態に戻って別の数字を試す。全ての組み合わせを系統的に探索するため、必ず解を見つける (解が存在すれば)。

数独ソルバーでの役割

仮置きと巻き戻しの手順

  1. 候補が最も少ないマスを選ぶ

    候補が 2 つのマスから始めれば、外れても試す枝は 1 本しか残らない。ここでの選び方が探索量を大きく左右する。

  2. 候補の 1 つを仮置きする

    確定した数字ではなく「仮の一手」として置き、後で取り消せるように控えておく。

  3. 制約伝播で確定できるマスを埋める

    仮置きの影響で候補が 1 つに絞られたマスを連鎖的に埋めていく。矛盾があれば早い段階で表面化する。

  4. 矛盾が生じたか

    はい

    直前の仮置きまで盤面を巻き戻し、同じマスの別の候補を試す。これがバックトラッキング。

    いいえ

    空きマスが残っていれば、最初の手順に戻って次のマスを選ぶ。

  5. すべてのマスが埋まったら解が完成

手順 1 から 4 を繰り返す反復構造で、巻き戻しても最後に選んだ仮置きだけを取り消すため、それまでに積み上げた確定分は無駄にならない。制約伝播を各段で挟むほど矛盾が早く見つかり、試す枝の数が減る。

制約伝播だけでは解けないパズルに対して、バックトラッキングが最終手段として機能する。候補が最も少ないマスから仮置きし、矛盾が生じたら巻き戻す。制約伝播と組み合わせることで、探索空間を大幅に削減できる。

人間の解法との違い

人間はバックトラッキング (推測) を避け、論理的に確定できる手順のみで解くことを好む。これはワーキングメモリの制約による。複数の仮定状態を同時に記憶・管理することは人間には困難だからだ。数独の難易度設計は「人間が推測なしで解けるか」を基準にしている。