Editing Backtracking (section)

==Description of the method==

The backtracking algorithm enumerates a set of ''partial candidates'' that, in principle, could be ''completed'' in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of ''candidate extension steps.''

Conceptually, the partial candidates are represented as the nodes of a [[tree structure]], the ''potential 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 tree [[recursion (computer science)|recursively]], from the root down, in [[depth-first search|depth-first order]].  At each node ''c'', the algorithm checks whether ''c'' can be completed to a valid solution.  If it cannot, the whole sub-tree rooted at ''c'' is skipped (''pruned'').  Otherwise, the algorithm (1) checks whether ''c'' itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all sub-trees  of ''c''.  The two tests and the children of each node are defined by user-given procedures.

Therefore, the ''actual 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.

===Pseudocode===
In order to apply backtracking to a specific class of problems, one must provide the data ''P'' for the particular instance of the problem that is to be solved, and  six [[procedural parameter]]s, ''root'', ''reject'', ''accept'', ''first'', ''next'', and ''output''. These procedures should take the instance data ''P'' as a parameter and should do the following:
# ''root''(''P''):  return the partial candidate at the root of the search tree.
# ''reject''(''P'',''c''):  return ''true'' only if the partial candidate ''c'' is not worth completing.
# ''accept''(''P'',''c''): return ''true'' if ''c'' is a solution of ''P'', and ''false'' otherwise.
# ''first''(''P'',''c''): generate the first extension of candidate ''c''.
# ''next''(''P'',''s''): generate the next alternative extension of a candidate, after the extension ''s''.
# ''output''(''P'',''c''):  use the solution ''c'' of ''P'', as appropriate to the application.

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

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

===Usage considerations===
The ''reject'' procedure should be a [[Boolean-valued function]] that returns ''true'' only if it is certain that no possible extension of ''c'' is a valid solution for ''P''.  If the procedure cannot reach a definite conclusion, it should return ''false''. An incorrect ''true'' result may  cause the ''backtrack'' procedure to miss some valid solutions.  The procedure may assume that ''reject''(''P'',''t'') returned ''false'' for every ancestor ''t'' of ''c'' in the search tree.

On the other hand, the efficiency of the backtracking algorithm depends on ''reject'' returning ''true'' for candidates that are as close to the root as possible.  If ''reject'' always returns ''false'', the algorithm will still find all solutions, but it will be equivalent to a brute-force search.

The ''accept'' procedure should return ''true'' if ''c'' is a complete and valid solution for the problem instance ''P'', and ''false'' otherwise.  It may assume that the partial candidate ''c'' and all its ancestors in the tree have passed the ''reject'' 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 for ''P'' can be further extended to yield other valid solutions.

The ''first'' and ''next'' procedures are used by the backtracking algorithm to enumerate the children of a node ''c'' of the tree, that is, the candidates that differ from ''c'' by a single  extension step.  The call ''first''(''P'',''c'') should yield the first child of ''c'', in some order; and the call ''next''(''P'',''s'') should return the next sibling of node ''s'', in that order.  Both functions should return a distinctive "NULL" candidate, if the requested child does not exist.

Together, the ''root'', ''first'', and ''next'' functions define the set of partial candidates and the potential search tree.  They should be chosen so that every  solution of ''P'' occurs somewhere in the tree, and no partial candidate occurs more than once.  Moreover, they should admit an efficient and effective ''reject'' predicate.

===Early stopping variants===
The pseudo-code above will call ''output'' for all candidates that are a solution to the given instance ''P''. 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 of [[central processing unit|CPU]] time.