Estimating the efficiency of backtrack programs

Author:
Donald E. Knuth

Journal:
Math. Comp. **29** (1975), 122-136

MSC:
Primary 68A20

MathSciNet review:
0373371

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: One of the chief difficulties associated with the so-called backtracking technique for combinatorial problems has been our inability to predict the efficiency of a given algorithm, or to compare the efficiencies of different approaches, without actually writing and running the programs. This paper presents a simple method which produces reasonable estimates for most applications, requiring only a modest amount of hand calculation. The method should prove to be of considerable utility in connection with D. H. Lehmer's branch-and-bound approach to combinatorial optimization.

**[1]**F. DE CARTEBLANCHE, "The colored cubes problem,"*Eureka*, v. 9, 1947, pp. 9-11.**[2]**T. R. DAWSON, "Echecs Feeriques," problem 186,*L'Echiquier*, (2), v. 2, 1930, pp. 1085-1086; solution in*L'Echiquier*, (2), v. 3, 1931, p. 1150.**[3]**T. R. DAWSON,*Caissa's Wild Roses*, C. M. Fox, Surrey, England, 1935; reprinted in*Five Classics of Fairy Chess*, Dover, New York, 1973.**[4]**T. R. DAWSON, "Chess facts and figures,"*Chess Pie III*, souvenir booklet of the International chess tournament, Nottingham, 1936, pp. 34-36.**[5]**Paul J. Gans,*Self-avoiding random walks. I. Simple properties of intermediate-length walks*, J. Chem. Phys.**42**(1965), 4159–4163. MR**0185685****[6]**Solomon W. Golomb and Leonard D. Baumert,*Backtrack programming*, J. Assoc. Comput. Mach.**12**(1965), 516–524. MR**0195585****[7]**N. T. Gridgeman,*The 23 Colored Cubes*, Math. Mag.**44**(1971), no. 5, 243–252. MR**1571968****[8]**Marshall Hall Jr. and D. E. Knuth,*Combinatorial analysis and computers*, Amer. Math. Monthly**72**(1965), no. 2, 21–28. MR**0172812****[9]**J. M. Hammersley and D. C. Handscomb,*Monte Carlo methods*, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR**0223065****[10]**J. M. Hammersley and K. W. Morton,*Poor man’s Monte Carlo*, J. Roy. Statist. Soc. Ser. B.**16**(1954), 23–38; discussion 61–75. MR**0064475****[11]**DONALD E. KNUTH, "Uncrossed knight's tours," (letter to the editor),*J. Recreational Math.*, v. 2, 1969, pp. 155-157.**[12]**Donald E. Knuth,*The art of computer programming*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**0378456****[13]**DÉNES KÖNIG,*Theorie der endlichen und unendlichen Graphen*, Leipzig, 1936; reprint, Chelsea, New York, 1950.**[14]**E. L. Lawler and D. E. Wood,*Branch-and-bound methods: A survey*, Operations Res.**14**(1966), 699–719. MR**0202469****[15]**DERRICK H. LEHMER, "Combinatorial problems with digital computers,"*Proc. Fourth Canadian Math. Congress*(1957), Univ. of Toronto Press, Toronto, 1959, pp. 160-173. See also:*Proc. Sympos. Appl. Math.*, vol. 6, Amer. Math. Soc., Providence, R. I., 1956, pp. 115, 124, 201.**[16]**DERRICK H. LEHMER, "The machine tools of combinatorics," Chapter 1 in*Applied Combinatorial Mathematics*, edited by Edwin F. Beckenbach, Wiley, New York, 1964, pp. 5-31.**[17]**ÉDOUARD LUCAS,*Récréations Mathématiques*, v. 1, Paris, 1882.**[18]**MICHIO MATSUDA & S. KOBAYASHI, "Uncrossed knight's tours," (letter to the editor),*J. Recreational Math.*, v. 2, 1969, pp. 155-157.**[19]**T. H. O'BIERNE,*Puzzles and Paradoxes*, Oxford Univ. Press, New York and London, 1965.**[20]**C. B. TOMPKINS, review of "Random-number generating dice," by Japanese Standards Association,*Math. Comp.*, v. 15, 1961, pp. 94-95.**[21]**R. J. Walker,*An enumerative technique for a class of combinatorial problems*, Proc. Sympos. Appl. Math., Vol. 10, American Mathematical Society, Providence, R.I., 1960, pp. 91–94. MR**0121306****[22]**Mark B. Wells,*Elements of combinatorial computing*, Pergamon Press, Oxford-New York-Toronto, Ont., 1971. MR**0277082****[23]**L. D. YARBROUGH, "Uncrossed knight's tours,"*J. Recreational Math.*, v. 1, 1968, pp. 140-142.

Retrieve articles in *Mathematics of Computation*
with MSC:
68A20

Retrieve articles in all journals with MSC: 68A20

Additional Information

DOI:
http://dx.doi.org/10.1090/S0025-5718-1975-0373371-6

Keywords:
Backtrack,
analysis of algorithms,
Monte Carlo method,
Instant Insanity,
color cubes,
knight's tours,
tree functions,
branch and bound

Article copyright:
© Copyright 1975
American Mathematical Society