(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."

Go to the Dictionary of Algorithms and Data Structures home page.

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