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 leads 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