Backtracking

バックトラッキングはすべての候補解を体系的に探索し、ある枝が実行不可能になった時点で選択を取り消して戻る。制約充足問題に使われる。

目的

N クイーンや数独のような組合せ探索や制約充足問題を解く。

解空間の木を深さ優先で探索し、各ステップで 1 つの候補を伸ばし、制約に違反したら戻る。枝刈り（制約伝播や限界判定）により探索空間を狭める。典型例は N クイーン、グラフ彩色、部分和問題である。