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. 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.
Expected Time Algorithm for the Graph Coloring Problem." Info. Proc. Let. 18,
119-121, 1984.