Rooted: Created page with "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 deter..."

2020-06-05T02:17:36Z

Created page with "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 deter..."

New page

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 ==

* [http://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search] at Wikipedia®
* [http://en.wikipedia.org/wiki/Depth-first_search Depth-first search] at Wikipedia®
* [http://en.wikipedia.org/wiki/Np-complete NP-complete] at Wikipedia®

[[Category:Solving Techniques]]

Backtrack - Revision history

Rooted: Created page with "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 deter..."