Backtrack programming techniques

ABSTRACT

The purpose of this paper is twofold. First, a brief exposition of the general backtrack technique and its history is given. Second, it is shown how the use of macros can considerably shorten the computation time in many cases. In particular, this technique has allowed the solution of two previously open combinatorial problems, the computation of new terms in a well-known series, and the substantial reduction in computation time for the solution to another combinatorial problem.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Ball, W.W.R. Mathematical Recreations and Essays, llth ed., revised by H.S.M. Coxeter. Macmillan, New York, 1960.
• 3: Bitner, J.R. Use of macros in backtrack programming. M.S. Th., U. of Illinois at Urbana-Champaign, Dep. of Computer Sci. Rep. UIUCDCS-R-74-687, 1974.
• 4: Bouwkamp, C.J. and Klarner, D.A. Packing a box with Y-pentacubes. J. Recreational Math. 3 (1970), 10-26.
• 5: Bunch, S.R. (personalcommunication).
• 6: Vaclav Chvatal , David A. Klarner , Donald E. Knuth, Selected combinatorial research problems., Stanford University, Stanford, CA, 1972
• 7: John G. Fletcher, A program to solve the Pentomino problem by the recursive use of macros, Communications of the ACM, v.8 n.10, p.621-623, Oct. 1965 [doi>10.1145/365628.365654]
• 8: Gardner, M. Mathematical games. Scientific American, Sept. 1966 and Jan. 1967.
• 9: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 10: Hall, M., and Knuth, D.E. Combinatorial analysis and computers. Amer. Math. Mo. 72, 2 (Part II) (Feb. 1965), 21-28.
• 11: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 12: Knuth, D.E. Estimating the efficiency of backtrack programs. Math. Comp. 29 (1975), 121-136.
• 13: Kraitchik, M. Mathematical Recreations. W.W. Norton, New York, 1942; Revised ed., Dover, New York, 1953.
• 14: Lawler, E.L., and Wood, D.E. Branch-and-bound methods: a survery. Oper. Res. 14 (1966), 699-719.
• 15: Lin, S. (personal communication).
• 16: Lucas, E., Rdcrdations Mathdmatiques, 2nd ed. Gauthier- Villars, Paris, 1891.
• 17: Nievergelt, J. (personal communication).
• 18: Peterson, G. (personal communication).
• 19: Preparata, F., and Nievergelt, J. Difference-preserving codes IEEE Trans. oll blf. Theory 20 (1974), 643-649.
• 20: Sainte-Lagu/5, M.A. Les Reseaux (ou Graphes). Memorial des Sciences Mathematiques, Fasc. 18, Gauthier-Villars, Paris, 1926.
• 21: Slagle, J.R. Artificial Intelligence--The Heuristic Programming Approach. McGraw-Hill, New York, 1971.
• 22: Tarjan, R.E. Depth first search and linear graph algorithms. SIAM J. Comput. 1 (1972), 146-160.
• 23: Tutte, W.T. The quest of the perfect square. Amer. Math. Mo. 72, 2 (Part II) (Feb. 1965), 29-35.
• 24: Walker, R.J. An enumerative technique for a class of combinatorial problems. Combblatorial Analysis (Proceedings of Symposium in Applied Mathematics, Vol. X), Amer. Math. Soc., Providence, R.I., 1960.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

Additional Classification:
  D. Software

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Keywords:
backtrack, combinatorial computing, depth-first search, difference-preserving codes, exhaustive search, macros, non-attacking queen's problem, pentominoes, squaring the square, tiling problems