Backtracking is a systematic way to go through all the possible configurations of a space. These configurations may be all possible arrangements of objects (permutations) or all possible ways of building a collection of them (subsets). Other applications may demand enumerating all spanning trees of a graph, all paths between two vertices, or all possible ways to partition the vertices into color classes.

What these problems have in common is that we must generate each one of
the possible configurations exactly once.
Avoiding both repetitions and missing configurations means that we must define
a systematic generation order among the possible configurations.
In combinatorial search, we represent our configurations by
a vector
, where each element is selected from
an ordered set of possible candidates for position *i*.
As shown below, this representation is general enough to encode
most any type of combinatorial object naturally.

The search procedure works by growing solutions one element at a time.
At each step in the search, we will have constructed
a partial solution with elements fixed for the first *k* elements of
the vector, where .
From this partial solution , we will
construct the set of possible candidates for the (*k*+1)st position.
We will then try to extend the partial solution by adding
the next element from .
So long as the extension yields a longer partial solution, we continue to
try to extend it.

However, at some point, might be empty, meaning that there is
no legal way to extend the current partial solution.
If so, we must *backtrack*, and replace , the last item in the
solution value, with the next candidate in .
It is this backtracking step that gives the procedure its name:

Backtrack(

A)Compute , the set of candidate first elements of solution

A.

k= 1while

k> 0 dowhile do (*advance*)

= the next element from

if is a solution, report it.

k=k+ 1compute , the set of candidate

kth elements of solutionA.

k=k- 1 (*backtrack*)

Backtracking constructs a tree of partial solutions,
where each vertex is a partial solution.
There is an edge from
*x* to *y* if node *y* was created by advancing from *x*.
This tree of partial solutions provides an alternative way to think
about backtracking, for the process of constructing the solutions
corresponds exactly to doing a depth-first traversal of the backtrack
tree.
Viewing backtracking as depth-first search yields a natural recursive
implementation of the basic algorithm:

Backtrack-DFS(

A,k)if is a solution, report it.

else

k=k+1compute

while do

= an element in

=

Backtrack(

a,k)

Although a breadth-first search could also be used to enumerate
all solutions, depth-first search is greatly preferred because of
the amount of storage required.
In depth-first search, the current
state of the search is completely represented
by the path from the root to the current search node, which requires space
proportional to the *height* of the tree.
In breadth-first search, the queue stores all the nodes at the current
level, which is proportional to the *width* of the search tree.
For most interesting problems, the width of the tree will grow exponentially
in its height.

To really understand how backtracking works, you must see how such objects as permutations and subsets can be constructed by defining the right state spaces. Examples of several state spaces are described below.

Mon Jun 2 23:33:50 EDT 1997