(algorithmic technique)
Definition: Find a solution by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points and alternate choices using recursion.
Note: Conceptually, a backtracking algorithm does a depth-first search of a tree of possible (partial) solutions. Each choice is a node in the tree.
Author: PEB
Explanation with the 8-queens problems and solving a maze; maze solving Java applet; short explanation, examples in C; FOLDOC's entry.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Mon Dec 5 10:54:23 2005.
HTML page formatted Mon Dec 5 10:54:46 2005.
Cite this as:
Paul E. Black, "backtracking", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/backtrack.html
