バックトラッキングとは

バックトラッキングとは、解の候補を順に作りながら探索し、途中で条件を満たさないと分かった時点でその先の探索をやめて一つ前の段階に戻り、別の選択肢を試す手法である。迷路の解法や、8クイーン問題のような組合せの問題で使われる。