A procedure mechanism for backtrack programming

ABSTRACT

One of the difficulties in using nondeterministic algorithms for the solution of combinatorial problems is that most programming languages do not include features capable of easily representing backtracking processes. This paper describes a procedure mechanism that uses coroutines as a means for the description and realization of nondeterministic algorithms. A solution to the eight queens problem is given to illustrate the application of the procedure mechanism to backtracking problems.

REFERENCES

• 1: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 2: 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]
• 3: Derrick H. Lehmer, Combinatorial problems with digital computers, Proc. of the Fourth Canadian Math. Congress, 1957, 160-173.
• 4: Robert J. Walker, An enumerative technique for a class of combinatorial problems, Proc. of the Symposium on Applied Mathematics, vol. 10, October 1960, 91-94.
• 5: Charles J. Prenner , Jay M. Spitzen , Ben Wegbreit, An implementation of backtracking for programming languages, Proceedings of the ACM annual conference, p.763-771, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805856]
• 6: John A. Self, Embedding non-determinism, Software—Practice and Experience, vol. 5, September 1975, 221-227.
• 7: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 8: Jacques Cohen and Eileen Carton, Nondeterministic fortran, Computer J., vol. 17, February 1974, 44-51.
• 9: Dianne E. Britton , Frederick C. Druseiks , Ralph E. Griswold , David R. Hanson , Richard A. Holmes, Procedure referencing environments in SL5, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.185-191, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811552]
• 10: Ralph E. Griswold and David R. Hanson, An overview of the SL5 programming language, SL5 project document SSLD1a, Dept. of Computer Science, The University of Arizona, Tucson, February 1976.
• 11: David R. Hanson, The syntax and semantics of SL5, SL5 project document SSLD2a, Dept. of Computer Science, The University of Arizona, Tucson, April 1976.
• 12: David R. Hanson and Ralph E. Griswold, The SL5 procedure mechanism, SL5 project document SSLD4, Dept. of Computer Science, The University of Arizona, Tucson, February 1976.
• 13: Ole Johan Dahl, Structured Programming, Academic Press, Inc., Orlando, FL, 1972
• 14: Niklaus Wirth, Program development by stepwise refinement, Communications of the ACM, v.14 n.4, p.221-227, April 1971 [doi>10.1145/362575.362577]
• 15: Niklaus Wirth, Algorithms + Data &equil Programs, Prentice-Hall, Englewood Cliffs, New Jersey, 1976, sec. 3.5.
• 16: Donald E. Knuth, Estimating the efficiency of backtrack programs, Mathematics of Computation, vol. 29, January 1975, 121-139.
• 17: Ole-Johan Dahl, SIMULA 67 common base language, (Norwegian Computing Center. Publication), 1968
• 18: Frederick C. Druseikis , John N. Doyle, A procedural approach to pattern matching in SNOBOL4, Proceedings of the 1974 annual conference, p.311-317, January 1974 [doi>10.1145/800182.810418]
• 19: Ralph E. Griswold, String scanning in SL5, SL5 project document SSLD5a, Dept. of Computer Science, The University of Arizona, Tucson, June 1976.
• 20: Ralph E. Griswold, String analysis and synthesis in SL5, Proceedings of the annual conference, p.410-414, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805628]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Coroutines

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

General Terms:
Algorithms, Languages