TOPICS
Search

Backtracking


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).


Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

Backtracking

Cite this as:

Weisstein, Eric W. "Backtracking." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Backtracking.html

Subject classifications