Backtracking is a class ofalgorithms for finding solutions to somecomputational problems, notablyconstraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.[1]
The classic textbook example of the use of backtracking is theeight queens puzzle, that asks for all arrangements of eightchessqueens on a standardchessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements ofk queens in the firstk rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned.
Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster thanbrute-force enumeration of all complete candidates, since it can eliminate many candidates with a single test.
Backtracking is an important tool for solvingconstraint satisfaction problems,[2] such ascrosswords,verbal arithmetic,Sudoku, and many other puzzles. It is often the most convenient technique forparsing,[3] for theknapsack problem and othercombinatorial optimization problems. It is also the program execution strategy used in the programming languagesIcon,Planner andProlog.
Backtracking depends on user-given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore ametaheuristic rather than a specific algorithm – although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time.
The term "backtrack" was coined by American mathematicianD. H. Lehmer in the 1950s.[4] The pioneer string-processing languageSNOBOL (1962) may have been the first to provide a built-in general backtracking facility.
The backtracking algorithm enumerates a set ofpartial candidates that, in principle, could becompleted in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence ofcandidate extension steps.
Conceptually, the partial candidates are represented as the nodes of atree structure, thepotential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further.
The backtracking algorithm traverses this search treerecursively, from the root down, indepth-first order. At each nodec, the algorithm checks whetherc can be completed to a valid solution. If it cannot, the whole sub-tree rooted atc is skipped (pruned). Otherwise, the algorithm (1) checks whetherc itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all sub-trees ofc. The two tests and the children of each node are defined by user-given procedures.
Therefore, theactual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test.
In order to apply backtracking to a specific class of problems, one must provide the dataP for the particular instance of the problem that is to be solved, and sixprocedural parameters,root,reject,accept,first,next, andoutput. These procedures should take the instance dataP as a parameter and should do the following:
The backtracking algorithm reduces the problem to the callbacktrack(P,root(P)), wherebacktrack is the following recursive procedure:
procedure backtrack(P, c)isif reject(P, c)then returnif accept(P, c)then output(P, c) s ← first(P, c)while s ≠ NULLdo backtrack(P, s) s ← next(P, s)
Thereject procedure should be aBoolean-valued function that returnstrue only if it is certain that no possible extension ofc is a valid solution forP. If the procedure cannot reach a definite conclusion, it should returnfalse. An incorrecttrue result may cause thebacktrack procedure to miss some valid solutions. The procedure may assume thatreject(P,t) returnedfalse for every ancestort ofc in the search tree.
On the other hand, the efficiency of the backtracking algorithm depends onreject returningtrue for candidates that are as close to the root as possible. Ifreject always returnsfalse, the algorithm will still find all solutions, but it will be equivalent to a brute-force search.
Theaccept procedure should returntrue ifc is a complete and valid solution for the problem instanceP, andfalse otherwise. It may assume that the partial candidatec and all its ancestors in the tree have passed thereject test.
The general pseudo-code above does not assume that the valid solutions are always leaves of the potential search tree. In other words, it admits the possibility that a valid solution forP can be further extended to yield other valid solutions.
Thefirst andnext procedures are used by the backtracking algorithm to enumerate the children of a nodec of the tree, that is, the candidates that differ fromc by a single extension step. The callfirst(P,c) should yield the first child ofc, in some order; and the callnext(P,s) should return the next sibling of nodes, in that order. Both functions should return a distinctive "NULL" candidate, if the requested child does not exist.
Together, theroot,first, andnext functions define the set of partial candidates and the potential search tree. They should be chosen so that every solution ofP occurs somewhere in the tree, and no partial candidate occurs more than once. Moreover, they should admit an efficient and effectivereject predicate.
The pseudo-code above will calloutput for all candidates that are a solution to the given instanceP. The algorithm can be modified to stop after finding the first solution, or a specified number of solutions; or after testing a specified number of partial candidates, or after spending a given amount ofCPU time.
Examples where backtracking can be used to solve puzzles or problems include:
The following is an example where backtracking is used for theconstraint satisfaction problem:
The generalconstraint satisfaction problem consists in finding a list of integersx = (x[1],x[2], …,x[n]), each in some range{1, 2, …,m}, that satisfies some arbitrary constraint (Boolean function)F.
For this class of problems, the instance dataP would be the integersm andn, and the predicateF. In a typical backtracking solution to this problem, one could define a partial candidate as a list of integersc = (c[1],c[2], …,c[k]), for anyk between 0 andn, that are to be assigned to the firstk variablesx[1],x[2], …,x[k]. The root candidate would then be the empty list (). Thefirst andnext procedures would then be
function first(P, c)is k ← length(c)if k = nthenreturn NULLelsereturn (c[1], c[2], ..., c[k], 1)
function next(P, s)is k ← length(s)if s[k] = mthenreturn NULLelsereturn (s[1], s[2], ..., s[k − 1], 1 + s[k])
Herelength(c) is the number of elements in the listc.
The callreject(P,c) should returntrue if the constraintF cannot be satisfied by any list ofn integers that begins with thek elements ofc. For backtracking to be effective, there must be a way to detect this situation, at least for some candidatesc, without enumerating all thosemn −kn-tuples.
For example, ifF is theconjunction of several Boolean predicates,F =F[1] ∧F[2] ∧ … ∧F[p], and eachF[i] depends only on a small subset of the variablesx[1], …,x[n], then thereject procedure could simply check the termsF[i] that depend only on variablesx[1], …,x[k], and returntrue if any of those terms returnsfalse. In fact,reject needs only check those terms that do depend onx[k], since the terms that depend only onx[1], …,x[k − 1] will have been tested further up in the search tree.
Assuming thatreject is implemented as above, thenaccept(P,c) needs only check whetherc is complete, that is, whether it hasn elements.
It is generally better to order the list of variables so that it begins with the most critical ones (i.e. the ones with fewest value options, or which have a greater impact on subsequent choices).
One could also allow thenext function to choose which variable should be assigned when extending a partial candidate, based on the values of the variables already assigned by it. Further improvements can be obtained by the technique ofconstraint propagation.
In addition to retaining minimal recovery values used in backing up, backtracking implementations commonly keep a variable trail, to record value change history. An efficient implementation will avoid creating a variable trail entry between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation.
An alternative to the variable trail is to keep atimestamp of when the last change was made to the variable. The timestamp is compared to the timestamp of a choice point. If the choice point has an associated time later than that of the variable, it is unnecessary to revert the variable when the choice point is backtracked, as it was changed before the choice point occurred.