Backtracking
Backtracking is an important tool for solving constraint satisfaction problems,[2] such as crosswords, verbal arithmetic, Sudoku, and many other puzzles.
It is therefore a metaheuristic 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.
[4] The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility.
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.
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.
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.
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 first and next procedures would then be 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 mn − k n-tuples.
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).
