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

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

数独ソルバーでの役割

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

人間の解法との違い

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