バックトラッキング
バックトラッキングのアルゴリズムは、単に正しい解を得るまで可能な組み合わせを試していくだけであり、一種の深さ優先探索である。探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試す。探索木を全部サーチしたとき、探索は失敗して終了する。
バックトラックは一般に再帰呼び出し関数として実装される。一回の呼び出しでは1つの変数に値を設定(束縛)して、それ以外を自由な変数として再帰的に呼び出す。バックトラッキングは深さ優先探索に似ているが、メモリ使用量が少なく、現在の解の状態を1つだけ保持し、更新していくだけである。
探索を高速化するため、値を選択して再帰呼び出しをする前に、アルゴリズムはその値を矛盾する未設定領域から削除する(前方チェック)か、全制約をチェックしてその新たな値による影響を求める(制約伝播)。これは、0/1 ナップサック問題やNクイーンの解を求める方法としては最も効率が良く、動的計画法よりもよい結果が得られる。