Backtracking

In computer science, backtracking is a recursive approach for finding solutions to some computational problems. Backtracking gradually finds candidate solutions and abandons candidates, i.e., "backtracks" when a candidate cannot be a good solution.

Pseudocode

A Sudoku solved by backtracking.

To apply backtracking to a problem, one must give the data P for an instance of the problem that is to be solved, and six procedures, root, abandon, accept, first, next, and save. These procedures should take the instance data P as a variable and should do the following:

1. root(P): return the partial candidate at the root of the search tree.
2. abandon(P,c): return true only if the partial candidate c is not worth completing.
3. accept(P,c): return true if c is a solution of P, and false otherwise.
4. first(P,c): generate the first extension of candidate c.
5. next(P,s): generate the next alternative extension of a candidate, after the extension s.
6. save(P,c): use the solution c of P

The backtracking algorithm reduces the problem to the call backtrack(root(P)), where backtrack is the following recursive procedure:

procedure backtrack(c) is
    if abandon(P, c) then return
    if accept(P, c) then save(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(s)
        s ← next(P, s)