backjump

Backjump is a backtracking technique used in constraint satisfaction problems (CSP) and propositional satisfiability (SAT) solving. It refers to non-chronological backtracking, where the solver may undo a sequence of assignments and continue from a previous, more relevant decision level rather than simply stepping back one level at a time. The aim is to reduce redundant search by skipping parts of the search tree that cannot lead to a solution.

In practice, backjumping relies on conflict analysis. When a conflict is detected, the solver analyzes the cause of the conflict and identifies which variable assignments contributed to it. Based on this analysis, the solver determines the most recent decision level that is implicated in the conflict and backtracks directly to that level. A new assignment is then attempted at that level, potentially with learned information that prunes previously explored paths.

Backjumping is often described in its variants, such as conflict-directed backjumping (CBJ) and non-chronological backtracking. In SAT solvers, this approach is closely connected with clause learning, where a conflict leads to the creation of a learned clause that helps prevent repeating the same conflict and supports earlier pruning of the search space.

Applications of backjumping are widespread in AI, particularly in CSP and SAT solvers for problems with complex or tightly coupled constraints. While it can dramatically reduce search effort on suitable problems, the technique adds overhead for conflict analysis and may not always yield improvements if conflicts do not reveal useful backjumps.