(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. maze solving Java applet. James D. Allen's short explanation.
An early exposition of this technique:
Solomon W. Golomb and Leonard D. Baumert, Backtrack Programming, Journal of ACM, 12(4):516-524, Oct 1965.
"This rather universal method was named 'backtrack' by Professor D. H. Lehmer of the University of California at Berkeley."
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 10 November 2008.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "backtracking", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 November 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/backtrack.html