Backtrack

Return to an earlier position in the solving path, after a contradiction or a dead end has been reached.

Backtracking is mainly used by Sudoku computer programs to determine the validity of a Sudoku by establishing that it has a unique solution.

With the aid of computer programs, human players can also backtrack using the Undo functionality. Players only need to backtrack after a guess or when using Trial & Error.

A popular metaphor for backtracking is Ariadne's Thread.

When using the term backtracking, there is a very strong implication that part of the algorithm being used is a depth first search. Think of the intermediate places where guesses (decisions) have to be made as branches of a tree. A depth first search starts at the trunk and follows the branches through the tree to each leaf (at which point there are no more decisions to be made). So for a Sudoku program the last guess will either be to solve the puzzle or to reach a point where there is an inconsistency. If an inconsistency is reached, the program backtracks to the last decision and chooses another path. On average you'd have to explore half the leaves on the tree to find the solution. Thus backtracking as an algorithmic technique is NP-complete. Being NP-complete is not a particular problem for Sudoku puzzles because the problem has a relatively small sample space. So a brute force computer program is actually reasonably quick.

External links

• Breadth-first search at Wikipedia®
• Depth-first search at Wikipedia®
• NP-complete at Wikipedia®