Different perspectives of the N-Queens problem

ABSTRACT

The N-Queens problem is a commonly used example in computer science. There are numerous approaches proposed to solve the problem. We introduce several definitions of the problem, and review some of the algorithms. We classify the algorithms for the N-Queens problem into 3 categories. The first category comprises the algorithms generating all the solutions for a given N. The algorithms in the second category are desinged to generate only the fundamental solutions [34]. The algorithms in the last category generate only one or several solutions but not necessarily all of them.

REFERENCES

• 1: Bruce Abramson , Moti Yung, Divide and conquer under global constraints: a solution to the N-queens problem, Journal of Parallel and Distributed Computing, v.6 n.3, p.649-662, June 1989 [doi>10.1016/0743-7315(89)90011-7]
• 2: W.Ahrens, Mathematische Unterhaltungen und Spiel~ vol. 1, Teubner, (1921).
• 3: J.A. Allis, W.M. Molaison, M.M. Tanik, The N- Queens Workstation User's Manual and Technical Reference Manual, SMU, TR 90-CSE-22, (june 1990).
• 4: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 5: Gilles Brassard , Paul Bratley, Algorithmics: theory & practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 6: Jacques Cohen, Non-Deterministic Algorithms, ACM Computing Surveys (CSUR), v.11 n.2, p.79-94, June 1979 [doi>10.1145/356770.356773]
• 7: C. Erbas, and M.M. Tanik, N-Queens Problem and Its Algorithms, SMU, TR 91-CSE-8, (February 1991).
• 8: C. Erbas, and M.M. Tanik, N-Queens Problem and Its Connections to the Polygons, SMU, TR 91-CSE-21, (June, 1991).
• 9: C. Erbas, and M.M. Tanik, "Storage Schemes for Parallel Memory Systems and the N-Queens Problem," The 15th ASME ETCE Conference, Computer Applications Symposium, Houston, Texas, (January 26-30, 1992).
• 10: C. Erbas, N. Rafraf, and M.M. Tanik, Magic Squares Constructed by the Uniform Step Method Provide Solutions to the N-Queens Problem, SMU, TR 91-CSE- 25, (August 1991).
• 11: B J Falkowski , L Schmitz, A note on the queens' problem, Information Processing Letters, v.23 n.1, p.39-46, July 20, 1986 [doi>10.1016/0020-0190(86)90128-6]
• 12: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 13: L.R. Foulds, and D.G. Johnson, "An application of graph theory and integer programming: Chessboard nonattacking puzzles," Math. Mag. 57 (2) (March 1984) 95-104.
• 14: C.F. Gauss, Briefwechsel zwischen C.F. Gauss und H.C. Schumacher, herausgeg, yon Peters, 6. Band, Altona (1865) 105-122.
• 15: J. Gingsburg, "Gauss's arithmetization of the problem of n queens," Scripta Math. 5 (1939) 63-66.
• 16: 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]
• 17: S. Gunther, "Zur mathematisches theorie des Schachbretts," Archiv der Mathematik und Physik 56 (1874) 281-292.
• 18: E.J. Hoffman, J.C. Loessi, and R.C. Moore, "Constructions for the Solution of the m Queens Problem," Mathematics Magazine, (March-April 1969), 66-72.
• 19: E. Lucas, Recreations mathematiques, 1891, Reprinted by A.Blanchard, Paris, 1960.
• 20: Bernard A. Nadel, Representation Selection for Constraint Satisfaction: A Case Study Using n-Queens, IEEE Expert: Intelligent Systems and Their Applications, v.5 n.3, p.16-23, June 1990 [doi>10.1109/64.54670]
• 21: P. Naur, "An experiment on program development," BY/" 12(1972) 347-365.
• 22: G. Polya, "Uber die 'doppelt-periodischen' iosungen des n-damen-problems," in W. Ahrens, Mathematische Unterhaltungen und Spiele, (1918) 364-374.
• 23: Matthias Reichling, A simplified solution of the n queens` problem, Information Processing Letters, v.25 n.4, p.253-255, June 17, 1987 [doi>10.1016/0020-0190(87)90171-2]
• 24: I. Rivin and R. Zabih, "An Algebraic Approach to Constraint Satisfaction Problems," Proceedings of the In:ernational Conference on Artificial Intelligence (IJCAI- 9), vol. 1, (1989), 284-289.
• 25: J.S. Rohl, "Generating Permutation by choosing," The Computer Journal, Vol. 21, Number 4, (1978), pp. 302-305.
• 26: J.S. Rohl, "Letter to the Editor," The Computer Journal, Vol. 22, Number 2, (1979) 191.
• 27: J.S. Rohl, "A faster lexiographical n-queens algorithm," Inforn~ Process. Le~ 17 (1983) 231-233.
• 28: D. R. Smith, KIDS: A Semiautomatic Program Development System, IEEE Transactions on Software Engineering, v.16 n.9, p.1024-1043, September 1990 [doi>10.1109/32.58788]
• 29: Rok Sosic , Jun Gu, A polynomial time algorithm for the N-Queens problem, ACM SIGART Bulletin, v.1 n.3, p.7-11, Oct. 1990 [doi>10.1145/101340.101343]
• 30: Harold S. Stone , Janice M. Stone, Efficient search techniques—an empirical study of the N-Queens problem, IBM Journal of Research and Development, v.31 n.4, p.464-474, July 1, 1987
• 31: Yoshiyasu Takefuji, Neural network parallel computing, Kluwer Academic Publishers, Norwell, MA, 1992
• 32: Murat Mehmet Tanik, A graph model for deadlock prevention., 1978
• 33: Murat M. Tanik , Townsend , Cheng , Stepoway, Graphics Programming with Turbo Pascal, Wordware Publishing Inc., Plano, TX, 1991
• 34: R.W. Topor, "Fundamental Solutions of the Eight Queens Problem," B/T, Vol. 22, (1982) 42-52.
• 35: 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]
• 36: A. M. Yaglom , I. M. Yaglom, Challenging mathematical problems with elementary solutions, Dover Publications, Inc., New York, NY, 1987

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS

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

General Terms:
Algorithms, Measurement, Theory