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.
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 E. Black.
Entry modified 10 November 2008.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "backtracking", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 10 November 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/backtrack.html