(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. 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 17 May 2021.
HTML page formatted Fri Jun 4 13:29:20 2021.
Cite this as:
Paul E. Black, "backtracking", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 17 May 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/backtrack.html