Backtracking is an intelligent way of gradually building the solution. It can be applied to constraint satisfaction problems like Sudoku, crossword, 8-queens puzzles, chess, etc.

Backtracking builds the solution incrementally. Partial solutions that do not satisfy the constraints are abandoned.

• Backtracking is a recursive approach.
• A solution in backtracking is expressed as an n-tuple $(x_1,x_2,\dots ,x_n)$, where $x_i$ is chosen from the finite set of choices $S_i$.
• Elements in the solution tuple are chosen such that they maximize or minimize the given criterion function $C(x_1,x_2,\dots ,x_n)$, by selecting or not selecting item $x_i$.
• Backtracking systematically searches the set of all feasible solutions, called the solution space, to solve the given problem.
• Each choice leads to a new set of partial solutions. Partial solutions are explored in DFS (depth first search) order, if the partial solutions satisfy the bounding function.
• If a partial solution does not satisfy the constraint, it will not be explored further. The algorithm backtracks from that point and explores the next possible candidate.
• Processing is represented using a state space tree.

Example

The numbers on the edges show the order in which the tree is explored in DFS order.

Constraints

While solving the problem, the backtracking method imposes two constraints.

1. Explicit constraints: These restrict the selection of $x_i$ from $S_i$. These are problem dependent, i.e. the $x_i$ values should be taken only from the given set.
2. Implicit constraints: These determine which tuples in the solution space satisfy the criterion function.

Terminology

1. Solution space

The collection of all feasible solutions is called the solution space.

2. State space

All the paths in the tree from the root to other nodes form the state space of the given problem.

3. Problem state

Each node in the state space tree represents a problem state.

4. Answer state

A leaf in the state space tree which satisfies the implicit constraints.

5. Solution state

A state S for which the path from the root to S represents a tuple in the solution space.

6. Live node

A node in the state space tree that is generated but whose children are yet to be generated.

7. E-node

A live node whose children are currently being explored. (E stands for expansion.)

8. Dead node

A node that is generated and either all its children are generated, or the node will not be expanded further due to a violation of the criterion function.

9. Bounding function

This kills the live node without exploring its children if the bound value of the live node crosses the bound limits.

10. Static tree

If a tree is independent of an instance of the problem being solved, it is called a static tree.

11. Dynamic tree

If the tree depends on an instance of the problem being solved, it is called a dynamic tree.

General backtracking method

Assume $(x_1,x_2,\dots ,x_i)$ is a path to a problem state, and let $T(x_1,\dots ,x_i)$ be the set of all possible values for $x_{i+1}$ such that $(x_1,x_2,\dots ,x_{i+1})$ is also a path to a problem state.

Assume the existence of a bounding function $B_{i+1}$, such that if $B_{i+1}(x_1,x_2,\dots ,x_{i+1})$ is false for a path $(x_1,x_2,\dots ,x_{i+1})$ from the root node to a problem state, then the path cannot be extended to reach an answer node. Thus the candidates for position i+1 of the solution vector $(x_1,\dots ,x_n)$ are those values which are generated by T and satisfy $B_{i+1}$.

• It follows a postorder traversal of a tree.
• Recursion is invoked by Backtrack(1).

Algorithm Backtrack(k)

Algorithm Backtrack(k)
/* This schema describes the backtracking process using recursion.
   On entering, the first k-1 values x[1], x[2], ..., x[k-1] of the
   solution vector x[1:n] have been assigned. x[ ] and n are global. */
{
    for (each x[k] ∈ T(x[1], ..., x[k-1])) do
    {
        if (B_k(x[1], x[2], ..., x[k]) ≠ 0) then
        {
            if (x[1], x[2], ..., x[k] is a path to an answer node)
                then write(x[1:k]);
            if (k < n) then Backtrack(k + 1);
        }
    }
}

Iterative version

Algorithm IBacktrack(n)
/* This schema describes the backtracking process.
   All solutions are generated in x[1:n] and printed as soon as
   they are determined. */
{
    k := 1;
    while (k ≠ 0) do
    {
        if (there remains an untried x[k] ∈ T(x[1], x[2], ..., x[k-1])
            and B_k(x[1], ..., x[k]) is true) then
        {
            if (x[1], ..., x[k] is a path to an answer node)
                then write(x[1:k]);
            k := k + 1;            // consider the next set
        }
        else k := k - 1;           // backtrack to previous set
    }
}