Backjumping

In backtracking algorithms, backjumping is a technique that reduces search space, therefore increasing efficiency. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels. In this article, a fixed order of evaluation of variables is used, but the same considerations apply to a dynamic order of evaluation. Image:Backtracking-no-backjumping.svg|A search tree visited by regular backtracking Image:Backtracking-with-backjumping.svg|A backjump: the grey node is not visited Whenever backtracking has tried all values for a variable without finding any solution, it reconsiders the last of the previously assigned variables, changing its value or further backtracking if no other values are to be tried. If is the current partial assignment and all values for have been tried without finding a solution, backtracking concludes that no solution extending exists. The algorithm then "goes up" to , changing 's value if possible, backtracking again otherwise. The partial assignment is not always necessary in full to prove that no value of lead to a solution. In particular, a prefix of the partial assignment may have the same property, that is, there exists an index such that cannot be extended to form a solution with whatever value for . If the algorithm can prove this fact, it can directly consider a different value for instead of reconsidering as it would normally do. The efficiency of a backjumping algorithm depends on how high it is able to backjump. Ideally, the algorithm could jump from to whichever variable is such that the current assignment to cannot be extended to form a solution with any value of . If this is the case, is called a safe jump. Establishing whether a jump is safe is not always feasible, as safe jumps are defined in terms of the set of solutions, which is what the algorithm is trying to find. In practice, backjumping algorithms use the lowest index they can efficiently prove to be a safe jump.