バックトラッキング
すなわち、問題の規則(制約)の一部をゆるめるのである。
バックトラッキングを制約プログラミング言語で使用する場合、言語機構そのものも制約情報の更新をしなければならないため、奇妙なオーバーヘッドが発生する。そのような言語では、PlannerやPrologのように、単純な深さ優先探索を使うのが適切である。
バックアップで必要最小限の値をリカバリするためだけでなく、値の更新履歴を記録するため、バックトラッキングの実装では一般に「変数の航跡(英語: variable trail)」を保持する。効率的な実装では、バックトラッキングは1つの操作で全変化を消去するため、選択点のない連続した変化についての変数の航跡を生成しない。
変数の航跡以外の手法として、変数に加えられた最新の変化のタイムスタンプを保持する手法がある。タイムスタンプは選択点のタイムスタンプと比較される。選択点のタイムスタンプがその変数のタイムスタンプより後であれば、その選択点がバックトラックされる場合にその変数をリバートする必要はない(その変数は、その選択点以前に変更されているため)。