バックトラッキング
ばっくとらっきんぐ
試行錯誤により解を探索するアルゴリズム。行き詰まったら前の状態に戻り別の選択肢を試す。
バックトラッキング (Backtracking) は、深さ優先探索に基づく問題解決アルゴリズムである。数独ソルバーでは、空きマスに数字を仮置きし、制約違反が発生したら前の状態に戻って別の数字を試す。全ての組み合わせを系統的に探索するため、必ず解を見つける (解が存在すれば)。
数独ソルバーでの役割
候補が最も少ないマスを選ぶ
候補が 2 つのマスから始めれば、外れても試す枝は 1 本しか残らない。ここでの選び方が探索量を大きく左右する。
候補の 1 つを仮置きする
確定した数字ではなく「仮の一手」として置き、後で取り消せるように控えておく。
制約伝播で確定できるマスを埋める
仮置きの影響で候補が 1 つに絞られたマスを連鎖的に埋めていく。矛盾があれば早い段階で表面化する。
矛盾が生じたか
はい
直前の仮置きまで盤面を巻き戻し、同じマスの別の候補を試す。これがバックトラッキング。
いいえ
空きマスが残っていれば、最初の手順に戻って次のマスを選ぶ。
すべてのマスが埋まったら解が完成
手順 1 から 4 を繰り返す反復構造で、巻き戻しても最後に選んだ仮置きだけを取り消すため、それまでに積み上げた確定分は無駄にならない。制約伝播を各段で挟むほど矛盾が早く見つかり、試す枝の数が減る。
制約伝播だけでは解けないパズルに対して、バックトラッキングが最終手段として機能する。空きマスに数字を仮置きし、矛盾が生じたら巻き戻す。どのマスを選ぶかで分岐の数は変わり、残り候補が少ないマスを先に選べばその時点の分岐数は小さくなる。候補の絞り込みを併用すれば、試す組み合わせを減らせる。
人間の解法との違い
紙とペンで解く場面では、仮置きによる探索 (推測) を避け、論理的に確定できる手順だけで解き進める方が好まれるとされることがある。理由としては、複数の仮定状態を同時に記憶・管理する負荷の大きさが挙げられる。