Backtracking is a method for solving combinatorial problems in which an algorithm runs forward until it reaches a dead end, retraces previous steps, and resumes the
search. Backtracking can greatly reduce the work of an exhaustive
search.
A backtracking search can be performed using 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. Machinery12, 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.