backjumping

Backjumping is a backtracking strategy used in constraint satisfaction problems (CSPs) and related search problems. Also known as nonchronological backtracking or conflict-directed backtracking, it aims to reduce redundant search by jumping to the most relevant earlier decision rather than stepping back one variable at a time when a dead end is reached.

During search, a dead end triggers an analysis of the reasons for the failure. The solver identifies a conflict set consisting of variables and constraints that contributed to the inconsistency. It then backjumps to the most recent variable in that set whose value can still be changed to potentially satisfy the constraints. This may be accompanied by recording a nogood, a combination of assignments known to be unsatisfiable together, to guide future decisions.

In practice, backjumping is often implemented as conflict-directed backtracking (CDB) and is used alongside constraint propagation techniques such as arc consistency. It is particularly effective when most failures are caused by a small subset of recent decisions, allowing large portions of the search tree to be skipped. The idea has influenced related approaches in SAT and modern CSP solvers, where non-chronological backtracking is combined with learning of nogoods or clauses to further prune search.

Limitations include the overhead of computing and maintaining conflict information, and the fact that the benefit depends on problem structure and ordering heuristics. When conflicts are widespread or propagation is expensive, backjumping may offer limited gains.