This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000170 Number of ways of placing n nonattacking queens on an n X n board.
(Formerly M1958 N0775)

%I M1958 N0775

%S 1,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184,

%T 14772512,95815104,666090624,4968057848,39029188884,314666222712,

%U 2691008701644,24233937684440,227514171973736,2207893435808352,22317699616364044,234907967154122528

%N Number of ways of placing n nonattacking queens on an n X n board.

%C For n > 3, a(n) is the number of maximum independent vertex sets in the n X n queen graph. - _Eric W. Weisstein_, Jun 20 2017

%C Number of nodes on level n of the backtrack tree for the n queens problem (a(n) = A319284(n, n)). - _Peter Luschny_, Sep 18 2018

%D M. Gardner, The Unexpected Hanging, pp. 190-2, Simon & Shuster NY 1969

%D Jieh Hsiang, Yuh-Pyng Shieh and Yao-Chiang Chen, The cyclic complete mappings counting problems, in Problems and Problem Sets for ATP, volume 02-10 of DIKU technical reports, G. Sutcliffe, J. Pelletier and C. Suttner, eds., 2002.

%D D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.

%D Massimo Nocentini, "An algebraic and combinatorial study of some infinite sequences of numbers supported by symbolic and logic computation", PhD Thesis, University of Florence, 2019. See Ex. 67.

%D M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 47.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. J. Walker, An enumerative technique for a class of combinatorial problems, pp. 91-94 of Proc. Sympos. Applied Math., vol. 10, Amer. Math. Soc., 1960.

%D M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 238.

%H Jordan Bell, Brett Stevens, <a href="http://dx.doi.org/10.1016/j.disc.2007.12.043">A survey of known results and research areas for n-queens</a>, Discrete Mathematics, Volume 309, Issue 1, Jan 06 2009, Pages 1-31.

%H D. Bill, <a href="http://www.durangobill.com/N_Queens.html">Durango Bill's The N-Queens Problem</a>

%H J. R. Bitner and E. M. Reingold, <a href="http://dx.doi.org/10.1145/361219.361224">Backtrack programming techniques</a>, Commun. ACM, 18 (1975), 651-656.

%H J. R. Bitner and E. M. Reingold, <a href="/A002562/a002562.pdf">Backtrack programming techniques</a>, Commun. ACM, 18 (1975), 651-656. [Annotated scanned copy]

%H P. Capstick and K. McCann, <a href="/A000170/a000170_1.pdf">The problem of the n queens</a>, apparently unpublished, no date (circa 1990?) [Scanned copy]

%H V. Chvatal, <a href="http://users.encs.concordia.ca/~chvatal/8queens.html">All solutions to the problem of eight queens</a>

%H V. Chvatal, <a href="/A002562/a002562_1.pdf">All solutions to the problem of eight queens</a> [Cached copy, pdf format, with permission]

%H Gheorghe Coserea, <a href="/A000170/a000170.txt">Solutions for n=8</a>.

%H Gheorghe Coserea, <a href="/A000170/a000170_1.txt">Solutions for n=9</a>.

%H Gheorghe Coserea, <a href="/A000170/a000170.mzn.txt">MiniZinc model for generating solutions</a>.

%H Matteo Fischetti, Domenico Salvagnin, <a href="https://www.researchgate.net/profile/Matteo_Fischetti/publication/322508723_Chasing_First_Queens_by_Integer_Programming/links/5a5cf3620f7e9b4f78396d0b/Chasing-First-Queens-by-Integer-Programming.pdf">Chasing First Queens by Integer Programming</a>, 2018.

%H J. Freeman, <a href="http://www.mathematica-journal.com/issue/v3i3/columns/freeman/index.html">A neural network solution to the n-queens problem</a>, The Mathematica J., 3 (No. 3, 1993), 52-56.

%H Ian P. Gent, Christopher Jefferson, Peter Nightingale, <a href="http://dx.doi.org/10.1613/jair.5512">Complexity of n-Queens Completion</a>, Journal of Artificial Intelligence Research 59 (2017), see p 816.

%H James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=jPcBU0Z2Hj8">The 8 Queen Problem</a>, Numberphile video (2015).

%H Kenji Kise, Takahiro Katagiri, Hiroki Honda and Toshitsugu Yuba, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=">Solving the 24-queens Problem using MPI on a PC Cluster</a>, Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communications (2004).

%H W. Kosters, <a href="http://www.liacs.nl/~kosters/nqueens/index.html">n-Queens bibliography</a>

%H V. Kotesovec, <a href="http://members.chello.cz/kotesovec/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf">Non-attacking chess pieces</a>, Sixth edition, 795 pages, Feb 02 2013 (minor update Mar 29 2016).

%H E. Masehian, H. Akbaripour, N. Mohabbati-Kalejahi, <a href="http://ccis2k.org/iajit/PDF/vol.11,no.6/5421.pdf">Solving the n Queens Problem using a Tuned Hybrid Imperialist Competitive Algorithm</a>, 2013;

%H E. Masehian, H. Akbaripour, N. Mohabbati-Kalejahi, <a href="http://dx.doi.org/10.1007/s10589-013-9578-z">Landscape analysis and efficient metaheuristics for solving the n-queens problem</a>, Computational Optimization and Applications, 2013; DOI 10.1007/s10589-013-9578-z.

%H Nasrin Mohabbati-Kalejahi, Hossein Akbaripour, Ellips Masehian, <a href="http://dx.doi.org/10.1007/978-3-319-11271-8_6">Basic and Hybrid Imperialist Competitive Algorithms for Solving the Non-attacking and Non-dominating n -Queens Problems</a>, Studies in Computational Intelligence Volume 577, 2015, pp 79-96. DOI 10.1007/978-3-319-11271-8_6.

%H J. Pope, D. Sonnier, <a href="http://dl.acm.org/citation.cfm?id=2600639">A linear solution to the n-Queens problem using vector spaces</a>, Journal of Computing Sciences in Colleges, Volume 29 Issue 5, May 2014 Pages 77-83.

%H T. B. Preußer, M. R. Engelhardt, <a href="https://dx.doi.org/10.1007%2Fs11265-016-1176-8">Putting Queens in Carry Chains, No. 27</a>, Journal of Signal Processing Systems, Volume 88, Issue 2, August 2017. (The title refers to the fact that the article discusses the case n = 27.)

%H Thomas B. Preußer, Bernd Nägel, Rainer G. Spallek, <a href="https://tu-dresden.de/ing/informatik/ti/vlsi/ressourcen/dateien/dateien_studium/dateien_lehstuhlseminar/vortraege_lehrstuhlseminar/ws_0809/vortrag.pdf?lang=en">Putting Queens in Carry Chains</a>, Slides, HIPEAC WRC’09.

%H E. M. Reingold, <a href="/A000170/a000170_2.pdf">Letter to N. J. A. Sloane</a>, Dec 27 1973

%H I. Rivin, I. Vardi and P. Zimmermann, <a href="http://www.jstor.org/stable/2974691">The n-queens problem</a>, Amer. Math. Monthly, 101 (1994), 629-639.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumIndependentVertexSet.html">Maximum Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueenGraph.html">Queen Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueensProblem.html">Queens Problem</a>

%H M. B. Wells, <a href="/A000170/a000170.pdf">Elements of Combinatorial Computing</a>, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]

%H Cheng Zhang, Jianpeng Ma, <a href="http://arxiv.org/abs/0808.4003">Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations</a>, arXiv:0808.4003 [cond-mat.stat-mech], 2008.

%F Strong conjecture: there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n; weak conjecture: lim n -> infinity (1/n) * log(n!/a(n)) = constant = 0.90.... - _Benoit Cloitre_, Nov 10 2002

%e a(2) = a(3) = 0, since on 2 X 2 and 3 X 3 chessboards there are no solutions.

%e For n=4 the a(4)=2 solutions are:

%e oxoo ooxo

%e ooox xooo

%e xooo ooox

%e ooxo oxoo

%Y See A140393 for another version. Cf. A002562, A065256.

%Y Cf. A036464 (2Q), A047659 (3Q), A061994 (4Q), A108792 (5Q), A176186 (6Q).

%Y Cf. A099152, A006717, A051906, A319284 (backtrack trees).

%K nonn,hard,nice,changed

%O 0,5

%A _N. J. A. Sloane_

%E Terms for n=21-23 computed by Sylvain PION (Sylvain.Pion(AT)sophia.inria.fr) and Joel-Yann FOURRE (Joel-Yann.Fourre(AT)ens.fr).

%E a(24) from Kenji KISE (kis(AT)is.uec.ac.jp), Sep 01 2004

%E a(25) from Objectweb ProActive INRIA Team (proactive(AT)objectweb.org), Jun 11 2005 [Communicated by Alexandre Di Costanzo (Alexandre.Di_Costanzo(AT)sophia.inria.fr)]. This calculation took about 53 years of CPU time.

%E a(25) has been confirmed by the NTU 25Queen Project at National Taiwan University and Ming Chuan University, led by Yuh-Pyng (Arping) Shieh, Jul 26 2005. This computation took 26613 days CPU time.

%E The NQueens-at-Home web site gives a different value for a(24), 226732487925864. Thanks to Goran Fagerstrom for pointing this out. I do not know which value is correct. I have therefore created a new entry, A140393, which gives the NQueens-at-home version of the sequence. - _N. J. A. Sloane_, Jun 18 2008

%E It now appears that this sequence (A000170) is correct and A140393 is wrong. - _N. J. A. Sloane_, Nov 08 2008

%E Added a(26) as calculated by Queens(AT)TUD [http://queens.inf.tu-dresden.de/]. - _Thomas B. Preußer_, Jul 11 2009

%E Added a(27) as calculated by the Q27 Project [https://github.com/preusser/q27]. - _Thomas B. Preußer_, Sep 23 2016

%E a(0) = 1 prepended by _Joerg Arndt_, Sep 16 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 13 03:51 EST 2018. Contains 318081 sequences. (Running on oeis4.)