Editing Backtracking (section)

==Examples==
[[File:Sudoku solved by bactracking.gif|thumb|A [[Sudoku]] solved by backtracking]]
Examples where backtracking can be used to solve puzzles or problems include:
* [[Puzzle]]s such as [[eight queens puzzle]], [[crosswords]], [[verbal arithmetic]], [[Algorithmics of sudoku|Sudoku]]{{refn|group=nb|See [[Sudoku solving algorithms]].}}, and [[Peg solitaire|Peg Solitaire]].
* [[Combinatorial optimization]] problems such as [[parsing]] and the [[knapsack problem]].
* Goal-directed programming languages such as [[Icon programming language|Icon]], [[Planner programming language|Planner]] and [[Prolog]], which use backtracking internally to generate answers.
* The [[DPLL algorithm]] for solving the [[Boolean satisfiability problem]].

The following is an example where backtracking is used for the [[constraint satisfaction problem]]:

===Constraint satisfaction===
The general [[constraint satisfaction problem]] consists in finding a list of integers {{nowrap|''x'' {{=}} (''x''[1], ''x''[2], …, ''x''[''n''])}}, each in some range {{nowrap|{1, 2, …, ''m''}}}, that satisfies some arbitrary constraint (Boolean function) ''F''.

For this class of problems, the instance data ''P'' would be the integers ''m'' and ''n'', and the predicate ''F''. In a typical backtracking solution to this problem, one could define a partial candidate as a list of integers {{nowrap|''c'' {{=}} (''c''[1], ''c''[2], …, ''c''[k])}}, for any ''k'' between 0 and ''n'', that are to be assigned to the first ''k'' variables {{nowrap|''x''[1], ''x''[2], …, ''x''[''k'']}}. The root candidate would then be the empty list (). The ''first'' and ''next'' procedures would then be

 '''function''' first(P, c) '''is'''
     k ← length(c)
     '''if''' k = n '''then'''
         '''return''' NULL
     '''else'''
         '''return''' (c[1], c[2], ..., c[k], 1)

 '''function''' next(P, s) '''is'''
     k ← length(s)
     '''if''' s[k] = m '''then'''
         '''return''' NULL
     '''else'''
         '''return''' (s[1], s[2], ..., s[k − 1], 1 + s[k])

Here ''length''(''c'') is the number of elements in the list ''c''.

The call ''reject''(''P'', ''c'') should return ''true'' if the constraint ''F'' cannot be satisfied by any list of ''n'' integers that begins with the ''k'' elements of ''c''. For backtracking to be effective, there must be a way to detect this situation, at least for some candidates ''c'', without enumerating all those ''m''<sup>''n'' − ''k''</sup> ''n''-tuples.

For example, if ''F'' is the [[Logical conjunction|conjunction]] of several Boolean predicates, {{nowrap|''F'' {{=}} ''F''[1] ∧ ''F''[2] ∧ … ∧ ''F''[''p'']}}, and each ''F''[''i''] depends only on a small subset of the variables {{nowrap|''x''[1], …, ''x''[''n'']}}, then the ''reject'' procedure could simply check the terms ''F''[''i''] that depend only on variables {{nowrap|''x''[1], …, ''x''[''k'']}}, and return ''true'' if any of those terms returns ''false''. In fact, ''reject'' needs only check those terms that do depend on ''x''[''k''], since the terms that depend only on {{nowrap|''x''[1], …, ''x''[''k'' − 1]}} will have been tested further up in the search tree.

Assuming that ''reject'' is implemented as above, then ''accept''(''P'', ''c'') needs only check whether ''c'' is complete, that is, whether it has ''n'' 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 the ''next'' 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 of [[constraint 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 a [[timestamp]] 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.