This site is supported by donations to The OEIS Foundation.



"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

(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,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184,14772512,

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

%U 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

%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 Kenji Kise, Takahiro Katagiri, Hiroki Honda and Toshitsugu Yuba: Solving the 24-queens Problem using MPI on a PC Cluster, Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communications (2004)

%D T. B. Preußer, M. R. Engelhardt, Putting Queens in Carry Chains, No. 27, J Sign Process Syst, 2016.

%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 Amazing Mathematical Object Factory, <a href="http://theory.cs.uvic.ca/amof/e_queeI.htm">Information on the n Queens problem</a>

%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="/A002562/a002562.pdf">Backtrack programming techniques</a>, Commun. ACM, 18 (1975), 651-656. [Annotated scanned copy]

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

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

%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed

%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 Bernd Nägel, Thomas B. Preußer, Rainer G. Spallek, <a href="http://queens.inf.tu-dresden.de/">Queens(AT)TUD</a> project website.

%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="http://queens.inf.tu-dresden.de/hipeac_wrc2009.pdf">Putting Queens in Carry Chains</a>, No. 27, J Sign Process Syst, 2016.

%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.

%K nonn,hard,nice

%O 1,4

%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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 20 01:30 EDT 2017. Contains 290821 sequences.