Cengiz Erbas
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.
- 1.B. Abramson and M. Yung, "Divide and conquer under global constraints: A solution to the n-queens problem," 3". Parall. Dist. Comp. 6 (1989) 649-662. Google Scholar
Digital Library
- 2.W.Ahrens, Mathematische Unterhaltungen und Spiel~ vol. 1, Teubner, (1921).Google Scholar
- 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).Google Scholar
- 4.C. Berge, Graphs and Hypergraphs, North-Holland Publishing Company, New York, (1973). Google ScholarDigital Library
- 5.G. Brassard, and P. Bratley, A lgorithmics Theory and Practice, Prentice-Hall, New lersey, (1988)~ Google ScholarDigital Library
- 6.J. Cohen, "Non-Deterministic Algorithms," Computing Surveys, Vol. I1, No. 2, (June 1979) 79-94. Google ScholarDigital Library
- 7.C. Erbas, and M.M. Tanik, N-Queens Problem and Its Algorithms, SMU, TR 91-CSE-8, (February 1991).Google Scholar
- 8.C. Erbas, and M.M. Tanik, N-Queens Problem and Its Connections to the Polygons, SMU, TR 91-CSE-21, (June, 1991).Google Scholar
- 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).Google Scholar
- 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).Google Scholar
- 11.B.J. Falkowski, and L. Schmitz, "A note on the queens' problem," Infort~ Process. Lett. 23 (1986) 39-46. Google ScholarDigital Library
- 12.R.W. Floyd, "Nondeterministic Algorithms," Journal ofACM, Vol. 14, No. 4, (October 1967) 636-644. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 14.C.F. Gauss, Briefwechsel zwischen C.F. Gauss und H.C. Schumacher, herausgeg, yon Peters, 6. Band, Altona (1865) 105-122.Google Scholar
- 15.J. Gingsburg, "Gauss's arithmetization of the problem of n queens," Scripta Math. 5 (1939) 63-66.Google Scholar
- 16.W.S. Golomb, and L.D. Baumert, "Backtrack Programming," J. ACM 12 (4) (1965) 516-524. Google ScholarDigital Library
- 17.S. Gunther, "Zur mathematisches theorie des Schachbretts," Archiv der Mathematik und Physik 56 (1874) 281-292.Google Scholar
- 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.Google ScholarCross Ref
- 19.E. Lucas, Recreations mathematiques, 1891, Reprinted by A.Blanchard, Paris, 1960.Google Scholar
- 20.B. Nadel, "Representation selection for constraint satisfaction: A case study using n-queens," IEEE Expert, June (1990) 16-23. Google ScholarDigital Library
- 21.P. Naur, "An experiment on program development," BY/" 12(1972) 347-365.Google Scholar
- 22.G. Polya, "Uber die 'doppelt-periodischen' iosungen des n-damen-problems," in W. Ahrens, Mathematische Unterhaltungen und Spiele, (1918) 364-374.Google Scholar
- 23.M. Reichling, "A Simplified Solution of the N queens' problem," Information Processing Letters, 25(1987) 253-255. Google ScholarDigital Library
- 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.Google Scholar
- 25.J.S. Rohl, "Generating Permutation by choosing," The Computer Journal, Vol. 21, Number 4, (1978), pp. 302-305.Google ScholarCross Ref
- 26.J.S. Rohl, "Letter to the Editor," The Computer Journal, Vol. 22, Number 2, (1979) 191.Google ScholarCross Ref
- 27.J.S. Rohl, "A faster lexiographical n-queens algorithm," Inforn~ Process. Le~ 17 (1983) 231-233.Google ScholarCross Ref
- 28.D.R. Smith, "KIDS: A semiautomatic program development system," IEEE Trans. Soft. Eng. 16 (9) (1990) 1024-1043. Google ScholarDigital Library
- 29.R. Sosic and J. Gu, "A polynomial time algorithm for the n-queens problem," SIGART 1 (3) (1990) 7-11. Google ScholarDigital Library
- 30.H.S. Stone and J.M. Stone, "Efficient search techniques - An empirical study of the n-queens problem," IBM J. Res. Develop. 31 (4) (July 1987) 464-474. Google ScholarDigital Library
- 31.Y. Takefuji, Neural Network Parallel Computing, Kluwer Academic Publishers, Hingham, MA, (1992). Google ScholarDigital Library
- 32.M.M. Tanik, A graph model for deadlock prevention, Phd Dissertation, Texas A&M University (1978). Google ScholarDigital Library
- 33.M.M. Tanik, IC Townsend, W. Cheng, and S.L. Stepoway, Graphics Programming with Turbo Pascal, Wordware, Dallas, TX, (1992). Google ScholarDigital Library
- 34.R.W. Topor, "Fundamental Solutions of the Eight Queens Problem," B/T, Vol. 22, (1982) 42-52.Google Scholar
- 35.N. Wirth, "Program development by stepwis~ reFmement," Comm. ACM, 14 (4) (1971) 221-227. Google ScholarDigital Library
- 36.A.M. Yaglom and I.M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Holden-Day, (1964) 92-98. Google ScholarDigital Library
Index Terms
- Different perspectives of the N-Queens problem
Recommendations
A polynomial time algorithm for the N-Queens problem
The n-queens problem is a classical combinatorial problem in the artificial intelligence (AI) area. Since the problem has a simple and regular structure, it has been widely used as a testbed to develop and benchmark new AI search problem-solving ...
Fundamental solutions of the eight queens problem
AbstractPrevious algorithms presented to solve the eight queens problem have generated the set of all solutions. Many of these solutions are identical after applying sequences of rotations and reflections. In this paper we present a simple, clear, ...
A group-based search for solutions of the n-queens problem
The n-queens problem is a well-known problem in mathematics, yet a full search for n-queens solutions has been tackled until now using only simple algorithms (with the exception of the Rivin-Zabih algorithm). In this article, we discuss optimizations ...
Comments