TOPICS
Search

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


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 Web Resource. https://mathworld.wolfram.com/Backtracking.html

Subject classifications