Estimating the efficiency of backtrack programs

Author:
Donald E. Knuth

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

MSC:
Primary 68A20

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

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-walks,"*J. Chem. Phys.*, v. 42, 1965, pp. 4159-4163. MR**32**#3147. MR**0185685 (32:3147)****[6]**SOLOMON W. GOLOMB & LEONARD D. BAUMERT, "Backtrack programming,"*J. Assoc. Comput. Mach.*, v. 12, 1965, pp. 516-524. MR**33**#3783. MR**0195585 (33:3783)****[7]**N. T. GRIDGEMAN, "The 23 colored cubes,"*Math. Mag.*, v. 44, 1971, pp. 243-252. MR**1571968****[8]**MARSHALL HALL, JR. & D. E. KNUTH, "Combinatorial analysis and computers,"*Amer. Math. Monthly*, v. 72, 1965, no. 2, part II, pp. 21-28. MR**30**#3030. MR**0172812 (30:3030)****[9]**J. M. HAMMERSLEY & D. C. HANDSCOMB,*Monte Carlo Methods*, Methuen, London; Barnes & Noble, New York, 1965. MR**36**#6114. MR**0223065 (36:6114)****[10]**J. M. HAMMERSLEY & K. W. MORTON, "Poor man's Monte Carlo,"*J. Roy. Statist. Soc. Ser. B*, v. 16, 1954, pp. 23-28. MR**16**, 287. MR**0064475 (16:287i)****[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,*Fundamental Algorithms*, The Art of Computer Programming, vol. 1, second edition Addison-Wesley, Reading, Mass., 1973. MR**0378456 (51:14624)****[13]**DÉNES KÖNIG,*Theorie der endlichen und unendlichen Graphen*, Leipzig, 1936; reprint, Chelsea, New York, 1950.**[14]**E. L. LAWLER & D. E. WOOD, "Branch-and-bound methods: A survey,"*Operations Research*, v. 14, 1966, pp. 699-719. MR**34**#2338. MR**0202469 (34:2338)****[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, Amer. Math. Soc., Providence, R. I., 1960, pp. 91-94. MR**22**#12048. MR**0121306 (22:12048)****[22]**MARK B. WELLS,*Elements of Combinatorial Computing*, Pergamon Press, Oxford and New York, 1971. MR**43**#2819. MR**0277082 (43:2819)****[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:
https://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