Backtracking
A method of solving combinatorial problems by means of an algorithm which is allowed to run forward until a dead end is reached, at which point previous steps are retraced and the algorithm is allowed to run forward again. Backtracking can greatly reduce the amount of work in an exhaustive search. Backtracking is implemented as Backtrack[s, partialQ, solutionQ] in the Wolfram Language package Combinatorica` .
Backtracking also refers to a method of drawing fractals by appropriate numbering of the corresponding tree diagram which does not require storage of intermediate results (Lauwerier 1991).
Baumert, L. D. and Golomb, S. W. "Backtrack Programming." J. Ass. Comp. Machinery 12, 516-524, 1965.
Knuth, D. E. "Estimating the Efficiency of Backtrack Programs." Math. Comput. 29, 122-136, 1975.
Lauwerier, H. A. Fractals: Endlessly Repeated Geometrical Figures. Princeton, NJ: Princeton University Press, 1991.
Skiena, S. "Backtracking and Distinct Permutations." §1.1.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 12-14, 1990.
Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, 1997.
Wilf, H. "Backtrack: An 
Expected Time
Algorithm for the Graph Coloring Problem." Info. Proc. Let. 18,
119-121, 1984.
Weisstein, Eric W. "Backtracking." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Backtracking.html
Contact the MathWorld Team
(1+e)/2
