n-Queens

NEW We (Pieter Bas Donkersteeg and Walter Kosters) produced a thorough update. At this moment we have 309 references.

Old stuff

We have a BiBTeX file with references to the n-queens problem; latest updates: June 1995, September 1998, February 1999, December 2000, March/April 2002. Some new references have been added in March/April 2002. And in 2008!

The references are also available in PostScript format (101 kB) or in PDF format (91 kB).

Thanks: Hendrik Jan Hoogeboom, Damien Wyart, Egbert Meissenburg.

To do:

• Bruce Abramson and Mordechai M. Yung, Construction through decomposition: A divide-and-conquer algorithm for the n-queens problem, 1986 [overlap with their 1989 paper?]
• Vijay Raghavan and Shankar M. Venkatesan, On Bounds for a Board Covering Problem, Information Processing Letters 25 (1987) 281-284
• Pauls "Das Maximalproblem der Damen auf dem Schachbrete", Deutsche Schachzeitung, Bd. 29, 1874, p. 129-134, 257-267.
• Intermédiaire des mathématiciens, t. I, 1894, p. 140/141 (J. Franel).
• H. Tarry, Assoc. franç. 26, Congrès de Saint Etienne, 1897, I, p. 176.
• Reference 3: Zwei Schachfragen. In: Schachzeitung. In monatlichen Heften ausgegeben von der Berliner Schachgesellschaft. Dritter Jahrgang, Berlin/London, 1848, S. 363. Wieviel Steine mit der Wirksamkeit der Dame können auf das im Übrigen leere Brett ...
• Wilhelm Ahrens, Achtdamenproblem, in: Encyklopädie der mathematischen Wissenschaften, Erster Band in zwei Teilen. Zweiter Teil, Leipzig 1900-1904, pp. 1082-1084 [pp. 1080-1093: Mathematische Spiele]
  Ahrens, W. "Das Achtköniginnenproblem." Ch. 9 in Mathematische Unterhaltungen und Spiele, dritte, verbesserte, anastatisch gedruckte aufl., Bd. 1. Leipzig, Germany: Teubner, pp. 211-284, 1921.
• Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 166-169, 1987.
• Campbell, P. J. "Gauss and the 8-Queens Problem: A Study in the Propagation of Historical Error." Historia Math. 4, 397-404, 1977.
• Dudeney, H. E. "The Eight Queens." ?300 in Amusements in Mathematics. New York: Dover, pp. 89 and 95-96, 1970.
• Erbas, C. and Tanik, M. M. "Generating Solutions to the N-Queens Problem Using 2-Circulants." Math. Mag. 68, 343-356, 1995.
• Gardner, M. "Patterns in Primes Are a Clue to the Strong Law of Small Numbers." Sci. Amer. 243, 18-28, Dec. 1980.
• Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.
• Ginsburg, J. "Gauss's Arithmetization of the Problem of n Queens." Scripta Math. 5, 63-66, 1939.
• Guy, R. K. "The n Queens Problem." ?C18 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 133-135, 1994.
• Kraitchik, M. "The Problem of the Queens" and "Domination of the Chessboard." ?10.3 and 10.4 in Mathematical Recreations. New York: W. W. Norton, pp. 247-256, 1942.
• Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 34-36, 1979.
• P. R. J. and Weakley, W. D. "Values of Domination Numbers of the Queen's Graph." Electronic J. Combinatorics 8, No. 1, R29, 1-19, 2001. http://www.combinatorics.org/Volume_8/Abstracts/v8i1r29.html.
• Pegg, E. Jr. "Math Games: Chessboard Tasks." Apr. 11, 2005. http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html.
• Riven, I.; Vardi, I.; and Zimmerman, P. "The n-Queens Problem." Amer. Math. Monthly 101, 629-639, 1994.
• Riven, I. and Zabih, R. "An Algebraic Approach to Constraint Satisfaction Problems." In Proc. Eleventh Internat. Joint Conference on Artificial Intelligence, Vol. 1, August 20-25, 1989. Detroit, MI: IJCAII, pp. 284-289, 1989.
• Ruskey, F. "Information on the n Queens Problem." http://www.theory.csc.uvic.ca/~cos/inf/misc/Queen.html.
• Sloane, N. J. A. Sequences A000170/M1958, A001366, A002562/M0180, A006717/M3005, and A007705/M4691 in "The On-Line Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.
• Sloane, N. J. A. and Plouffe, S. Figure M0180 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.
• Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 29-30, 1999.
• Vardi, I. "The n-Queens Problems." Ch. 6 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 107-125, 1991.
• Velucchi, M. "For Me, This Is the Best Chess-Puzzle: Non-Dominating Queens Problem." http://anduin.eldar.org/~problemi/papers.html.
• Velucchi, M. "Different Dispositions on the ChessBoard." http://anduin.eldar.org/~problemi/papers.html.
• Watkins, J. Across the Board: The Mathematics of Chessboard Problems. Princeton, NJ: Princeton University Press, 2004
• Jeremiah Barr and Shrisha Rao, The n-queens problem in higher dimensions, Elemente der Mathematik 61 (2006) 133-137.
• Matthias R. Engelhardt, A group-based search for solutions of the n-queens problem, Discrete Mathematics, Volume 307, Issue 21, 6 October 2007, Pages 2535-2551. http://dx.doi.org/10.1016/j.disc.2007.01.007

References

1. Bruce Abramson and Mordechai M. Yung. Divide and Conquer under Global Constraints: A Solution to the N-Queens Problem. Journal of Parallel and Distributed Computing, 6:649-662, 1989.

2. Wilhelm Ahrens. Mathematische Unterhaltungen und Spiele. B.G. Teubner, 1910.

3. (Author - Anonymous). (Title - Unknown). Berliner Schachgesellschaft, 3:363, 1848.

4. W.W. Rouse Ball. Mathematical Recreations and Essays, page 113. MacMillan and Co., 1926.

5. B.T. Bennett and R.B. Potts. Arrays and Brooks. Journal for the Australian Mathematical Society, pages 23-31, 1967.

6. Bo Bernhardsson. Explicit Solution to the n-Queens Problems for all n. ACM SIGART Bulletin, 2:7, 1991.

7. J.R. Bitner and E.M. Reingold. Backtrack Programming Techniques. Communications of the ACM, 18:651-656, 1975.

8. Ivan Bratko. Prolog Programming for Artificial Intelligence. Addison-Wesley, 2nd edition, 1990.

9. A. Bruen and R. Dixon. The n-Queens Problem. Discrete Mathematics, 12:393-395, 1975.

10. NEW P.J. Campbell, Gauss and the Eight Queens Problem, A Study in Miniature of the Propagation, Historia Mathematica, 4:397-404, 1977.

11. A.P. Burger, Ernest J. Cockayne and C.M. Mynhardt. Domination and Irredundance in the Queens' Graph. Discrete Mathematics, 163:47-66, 1997.

12. NEW Grant Cairns, Queens on Non-square Tori, The Electronic Journal of Combinatorics, 8:N6, 2001.

13. A.K. Chandra. Independent Permutations, as Related to a Problem of Moser and a Theorem of Pólya. Journal of Combinatorial Theory, A16:111-120, 1974.

14. R.M. Clapp, T.N. Mudge and R.A. Volz. Solutions to the n Queens Problem Using Tasking in Ada. SIGPLAN Notices, 21:99-110, 1986.

15. Ernest J. Cockayne and Stephen T. Hedetniemi. On the Diagonal Queens Domination Problem. Journal of Combinatorial Theory, A42:137-139, 1986.

16. K.D. Crawford. Solving the n-Queens Problem Using Genetic Algorithms. In Proceedings ACM/SIGAPP Syposium on Applied Computing, Kansas City, pages 1039-1047, 1992.

17. Paul Cull and Rajeev Pandy. Isomorphism and the N-Queens Problem. SIGCSE Bulletin, 26:29-36, 1994.

18. Onur Demiroers, Nader Rafraf and Murat M. Tanik. Obtaining N-Queens Solutions from Magic Squares and Constructing Magic Squares from N-Queens Solutions. Journal of Recreational Mathematics, 24:272-280, 1992.

19. Henry Ernest Dudeney. Amusements in mathematics, Chapter on Chessboard Problems, pages 89,215. Dover Publications, 1917. (Many reprints from 1919 to 1946; first Dover reprint: 1948.)

20. A.E. Eiben, P.-E. Raué and Zs. Ruttkay. Solving Constraint Satisfaction Problems Using Genetic Algorithms. In Proceedings of the 1st IEEE World Conference on Computational Intelligence, pages 542-547. IEEE Service Center, 1994.

21. A.E. Eiben, P.-E. Raué and Zs. Ruttkay. GA-easy and GA-hard Constraint Satisfaction Problems. In Proceedings of the ECAI-94 workshop on Constraint Processing, number 923 in Lecture Notes in Computer Science. Springer-Verlag, 1995.

22. C. Erbas and M.M. Tanik. Storage Schemes for Parallel Memory Systems and the N-Queens Problem. In Proceedings of the 15th Anniversary of the ASME ETCE Confererence, Computer Applications Symposium, 1992.

23. C. Erbas, S. Sarkeshik and M.M. Tanik. Different Perspectives of the N-Queens Problem. In Proceedings of the ACM 1992 Computer Science Conference, 1992.

24. C. Erbas, M.M. Tanik and Z. Aliyazicioglu. Linear Congruence Equations for the Solutions of the N-Queens Problem. Information Processing Letters, 41:301-306, 1992.

25. Cengiz Erbas and Murat M. Tanik. Generating Solutions to the N-Queens Problem Using 2-Circulants. Mathematics Magazine, 68:343-356, 1995.

26. Bernd-Jürgen Falkowski and Lothar Schmitz. A Note on the Queens' Problem. Information Processing Letters, 23:39-46, 1986.

27. J.P. Fillmore and S.G. Williamson. On Backtracking: A Combinatorial Description of the Algorithm. SIAM Journal on Computing, 3:41-55, 1974.

28. John Foley. Manchester Dataflow Machine: Preliminary Benchmark Test Evaluation. Technical Report UMCS-87-11-2, University of Manchester, Computer Science Department, November 1987.

29. L.R. Foulds and D.G. Johnson. An Application of Graph Theory and Integer Programming: Chessboard Nonattacking Puzzles. Mathematical Magazine, 57:95-104, 1984.

30. Martin Gardner. Mathematical Games. Scientific American, 227:176-182, 1972.

31. J. Ginsburg. Gauss's Arithmetization of the Problem of 8 Queens. Scripta Mathematica, 5:63-66, 1939.

32. M.E. Goldsby. Solving the "N<=8 Queens'' Problem with CSP and Modula-2. SIGPLAN Notices, 22:43-52, 1987.

33. Solomon W. Golomb and L. Baumert. Backtrack Programming. Journal of the ACM, 12:516-524, 1965.

34. Solomon W. Golomb. Sphere Packing, Coding Metrics and Chess Puzzles. In R.C. Rose, editor, Chapel Hill Conference on Combinatorial Mathematics and its Applications, pages 176-189, 1970.

35. J.S. Gray. Is Eight Enough? - The Eight Queens Problem Re-examined. SIGCSE Bulletin, 25:39-44,51, 1993.

36. NEW Jun Gu. On a General Framework for Large-scale Constraint-based Optimization. ACM SIGART Bulletin, 2:8, 1991.

37. S. Günther. (Unknown). Archiv der Mathematik und Physik, 56:281-292, 1874.
    Is this joint work with James Whitbread Lee Glaisher on determinants?

38. NEW Jiawei Han, Ling Liu and Tong Lu, Evaluation of Declarative n-Queens Recursion: A Deductive Database Approach, Information Sciences, 105:69-100, 1998.

39. B. Hansche and W. Vucenic. On the n-Queens Problem. Notices of the American Mathematical Society, 20:568, 1973.

40. Peter Hayes. A Problem of Chess Queens. Journal of Recreational Mathematics, 24:264-271, 1992.

41. Olof Heden. On the Modular n-Queen Problem. Discrete Mathematics, 102:155-161, 1992.

42. Olof Heden. Maximal Partial Spreads and the Modular n-Queen Problem. Discrete Mathematics, 120:75-91, 1993.

43. Sandra M. Hedetniemi, Stephen T. Hedetniemi and R. Reynolds. Combinatorial problems on chessboards: II. Chapter 6 in Domination in Graphs: Advanced Topics, Teresa W. Haynes, Stephen T. Hedetniemi and Peter J. Slater, Eds., Marcel Dekker, New York (1998), pp. 133-162.

44. Stephen T. Hedetniemi, A. A. McRae and D.A. Parks. Complexity results. Chapter 9 in Domination in Graphs: Advanced Topics, Teresa W. Haynes, Stephen T. Hedetniemi and Peter J. Slater, Eds., Marcel Dekker, New York (1998), pp. 233-269.

45. E.J. Hoffman, J.C. Loessi and R.C. Moore. Constructions for the Solution of the m Queens Problem. National Mathematics Magazine, March-April:66-72, 1969.

46. Abdollah Homaifar, Joseph Turner, and Samia Ali. The n-Queens Problem and Genetic Algorithms. In Proceedings IEEE Southeast Conference, Volume 1, pages 262-267, 1992.

47. F.K. Hwang and Ko-Wei Lih. Latin Squares and Superqueens. Journal of Combinatorial Theory, A35:110-114, 1983.

48. Laxmikant V. Kalé. An Almost Perfect Heuristic for the N Nonattacking Queens Problem. Information Processing Letters, 34:173-178, 1990.

49. J.G. Keating. Hopfield Networks, Neural Data Structures and the Nine Flies Problem: Neural Network Programming Projects for Undergraduates. SIGCSE Bulletin, 25:33-37,40,60, 1993.

50. D.A. Klarner. The Problem of Reflecting Queens. American Mathematical Monthly, 74:953-955, 1967.

51. Torleiv Kløve. The Modular n-Queen Problem. Discrete Mathematics, 19:289-291, 1977.

52. Torleiv Kløve. The Modular n-Queen Problem II. Discrete Mathematics, 36:33-48, 1981.

53. NEW D.E. Knuth, Dancing Links, pp 187-214 in: Millennial Perspectives in Computer Science, editors: Jim Davies, Bill Roscoe and Jim Woodcock; Palgrave, 2000.
    LINK

54. F.C. Kuechmann. Solving the Eight Queens Problem. MacTech magazine: for Macintosh programmers & developers, 13:20-27, 1997.

55. J. Mandziuk and B. Macukow. A Neural Network Designed to Solve the N-Queens Problem. Biological Cybernetics, 66:375-379, 1992.

56. J. Mandziuk. Solving the N-Queens Problem with a Binary Hopfield-type Network. Synchronous and Asynchronous Model. Biological cybernetics: communication and control in organisms and automata, 72:439-446, 1995.

57. Steven Minton, Mark D. Johnston, Andrew B. Philips and Philip Laird. Minimizing Conflicts: A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems. Artificial Intelligence, 58:161-205, 1992.

58. P. Morris. On the density of solutions in equilibrium points for the queens problem. In Proceedings AAAI-92, 428-433, 1992.

59. B.A. Nadel. Representation Selection for Constraint Satisfaction: A Case Study Using n-Queens. IEEE Expert, June:16-23, 1990.

60. Franz Nauck. Schach. Illustrierter Zeitung, 361:352, 1850.

61. P. Naur. An Experiment on Program Development. BIT, 12:347-365, 1972.

62. NEW E. Netto, Lehrbuch der Combinatorik, B.G. Teubner, Leipzig, 1901.

63. Scott P. Nudelman. The Modular n-Queens Problem in Higher Dimensions. Discrete Mathematics, 146:159-167, 1995.

64. Sang Bong Oh. An Analytical Evidence for Kalé's Heuristic for the N Queens Problem. Information Processing Letters, 46:51-54, 1993.

65. Alton T. Olson. The Eight Queens Problem. Journal of Computers in Mathematics and Science Teaching, 12:93, 1993.

66. G. Pólya. Mathematische Unterhaltungen und Spiele, II Band, 2 Auflage, (author: Wilhelm Ahrens), chapter Über die "doppelt-periodischen" Lösungen des n-Damen-Problems. B.G. Teubner, Leipzig und Berlin, 1918. pp. 364-374. Reprinted in Pólya: Collected works, vol. V, pp. 237-247.

67. Matthias Reichling. A Simplified Solution of the N Queens' Problem. Information Processing Letters, 25:253-255, 1987.

68. I. Rivin and R. Zabih. A Dynamic Programming Solution to the n-Queens Problem. Information Processing Letters, 41:253-256, 1992.

69. I. Rivin, I. Vardi and P. Zimmermann. The n-Queens Problem. The American Mathematical Monthly, 101:629-639, 1994.

70. J.S. Rohl. A Faster Lexicographical n-Queens Algorithm. Information Processing Letters, 17:231-233, 1983.

71. J.T. Schwartz, R.B.K. Dewar, E. Dubinsky and E. Schonberg. Programming with Sets, An Introduction to SETL, chapter 7, pages 312-314. Springer-Verlag, 1986.

72. NEW Oron Shagrir, A Neural Net with Self-inhibiting Units for the N-queens Problem, International Journal of Neural Systems 3:249-252, 1992.

73. Rok Sosic and Jun Gu. Fast N-Queen Search on VAX and Bobcat Machines. AI Project Report, February, 1988.

74. Rok Sosic and Jun Gu. How to Search For Million Queens. Technical Report UUCS-TR-88-008, Department of Computer Science, University of Utah, 1988.

75. Rok Sosic and Jun Gu. A Polynomial Time Algorithm for the N-Queens Problem. SIGART Bulletin, 1:7-11, 1990.

76. Rok Sosic and Jun Gu. 3,000,000 Queens in Less Than One Minute. SIGART Bulletin, 2:22-24, 1991.

77. Rok Sosic and Jun Gu. Fast Search Algorithms for the N-Queens Problem. IEEE Transactions on Systems, Man and Cybernetics, 21:1572-1576, 1991.

78. Rok Sosic and Jun Gu. Efficient Local Search with Conflict Minimization: A Case Study of the n-Queens Problem. IEEE Transactions on Knowledge and Data Engineering, 6:661-668, 1994.

79. Rok Sosic. A Parallel Search Algoritm for the n-Queens Problem. In Parallel Computing and Transputer Conference, Wollongong, pages 162-172. IOS Press, 1994.

80. H.S. Stone and J.M. Stone. Efficient Search Techniques - An Empirical Study of the N-Queens Problem. IBM Journal of Research and Development, 31:464-474, 1987.

81. T. Tambouratzis. A Simulated Annealing Artificial Neural Network Implementation of the N-Queens Problem. International Journal of Intelligent Systems, 12:739-752, 1997.

82. W.F.D. Theron and G. Geldenhuys. Domination by Queens on a Square Beehive. Discrete Mathematics, 178:213-220, 1998.

83. Alexey Tolpygo, Follow-up: Queens on a Cylinder. Quantum: The Student Magazine of Math and Science, 6:38-42, 1996.

84. Robert A. Wagner and Robert H. Geist. The Crippled Queen Placement Problem. Technical report, Duke University, 1984.

85. Niklaus Wirth. Program Development by Stepwise Refinement. Communications of the ACM, 14:221-227, 1971.

86. A.M. Yaglom and I.M. Yaglom. Challenging Mathematical Problems with Elementary Solutions. Holden-Day, 1964.

87. Hiroaki Yoshio, Takayuki Baba, Nobuo Funabiki and Seishi Nishikawa. Proposal of an N-Parallel Computation Method for a Neural Network for the N Queens Problem. Electronics and Communications in Japan, 80:12-20, 1997.

88. C.K. Yuen and M.D. Feng. Breadth-First Search in the Eight Queens Problem. SIGPLAN Notices. 29:51-55, 1994.

Questions/remarks to: kosters@liacs.nl.

18 February 2008 — http://www.liacs.nl/home/kosters/indexold.html