

A000170


Number of ways of placing n nonattacking queens on an n X n board.
(Formerly M1958 N0775)


80



1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884, 314666222712, 2691008701644, 24233937684440, 227514171973736, 2207893435808352, 22317699616364044, 234907967154122528
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

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
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
Number of permutations of [1...n] such that p(j)p(i) != ji for i<j.  Xiangyu Chen, Dec 24 2020
M. Simkin shows that the number of ways to place n mutually nonattacking queens on an n X n chessboard is ((1 +/ o(1))*n*exp(c))^n, where c = 1.942 +/ 0.003. These are approximately (0.143*n)^n configurations.  Peter Luschny, Oct 07 2021


REFERENCES

M. Gardner, The Unexpected Hanging, pp. 1902, Simon & Shuster NY 1969
Jieh Hsiang, YuhPyng Shieh and YaoChiang Chen, The cyclic complete mappings counting problems, in Problems and Problem Sets for ATP, volume 0210 of DIKU technical reports, G. Sutcliffe, J. Pelletier and C. Suttner, eds., 2002.
D. E. Knuth, The Art of Computer Programming, Volume 4, Prefascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.
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.
W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed., New York, Dover, 1987, pp. 166172 (The Eight Queens Problem).
M. A. SainteLaguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, GauthierVillars, Paris, 1926, p. 47.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. J. Walker, An enumerative technique for a class of combinatorial problems, pp. 9194 of Proc. Sympos. Applied Math., vol. 10, Amer. Math. Soc., 1960.
M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 238.


LINKS

Table of n, a(n) for n=0..27.
Jordan Bell and Brett Stevens, A survey of known results and research areas for nqueens, Discrete Mathematics, Volume 309, Issue 1, Jan 06 2009, Pages 131.
D. Bill, Durango Bill's The NQueens Problem
J. R. Bitner and E. M. Reingold, Backtrack programming techniques, Commun. ACM, 18 (1975), 651656.
J. R. Bitner and E. M. Reingold, Backtrack programming techniques, Commun. ACM, 18 (1975), 651656. [Annotated scanned copy]
Candida Bowtell and Peter Keevash, The nqueens problem, arXiv:2109.08083 [math.CO] 2021.
P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]
V. Chvatal, All solutions to the problem of eight queens
V. Chvatal, All solutions to the problem of eight queens [Cached copy, pdf format, with permission]
Gheorghe Coserea, Solutions for n=8.
Gheorghe Coserea, Solutions for n=9.
Gheorghe Coserea, MiniZinc model for generating solutions.
Matteo Fischetti and Domenico Salvagnin, Chasing First Queens by Integer Programming, 2018.
Matteo Fischetti and Domenico Salvagnin, Finding First and MostBeautiful Queens by Integer Programming, arXiv:1907.08246 [cs.DS], 2019.
J. Freeman, A neural network solution to the nqueens problem, The Mathematica J., 3 (No. 3, 1993), 5256.
Ian P. Gent, Christopher Jefferson and Peter Nightingale, Complexity of nQueens Completion, Journal of Artificial Intelligence Research 59 (2017), see p 816.
Eric Grigoryan, Investigation of the Regularities in the Formation of Solutions nQueens Problem, Modeling of Artificial Intelligence, 2018, 5(1), 321.
E. Grigoryan, Linear algorithm for solution nQueens Completion problem, arXiv:1912.05935 [cs.AI], 2019.
James Grime and Brady Haran, The 8 Queen Problem, Numberphile video (2015).
Michael Han, Tanya Khovanova, Ella Kim, Evin Liang, Miriam Lubashev, Oleg Polin, Vaibhav Rastogi, Benjamin Taycher, Ada Tsui and Cindy Wei, Fun with Latin Squares, arXiv:2109.01530 [math.HO], 2021.
Kenji Kise, Takahiro Katagiri, Hiroki Honda and Toshitsugu Yuba, Solving the 24queens Problem using MPI on a PC Cluster, Technical Report UECIS20046, Graduate School of Information Systems, The University of ElectroCommunications (2004).
D. E. Knuth, Donald Knuth's 24th Annual Christmas Lecture: Dancing Links, Stanfordonline, Video published on YouTube, Dec 12, 2018.
W. Kosters, nQueens bibliography
Vaclav Kotesovec, Nonattacking chess pieces, Sixth edition, 795 pages, Feb 02 2013 (minor update Mar 29 2016).
Zur Luria, New bounds on the number of nqueens configurations, arXiv:1705.05225 [math.CO], 2017.
Zur Luria, Michael Simkin, A lower bound for the nqueens problem, arXiv:2105.11431 [math.CO], 2021.
E. Masehian, H. Akbaripour and N. MohabbatiKalejahi, Solving the n Queens Problem using a Tuned Hybrid Imperialist Competitive Algorithm, 2013.
E. Masehian, H. Akbaripour and N. MohabbatiKalejahi, Landscape analysis and efficient metaheuristics for solving the nqueens problem, Computational Optimization and Applications, 2013; DOI 10.1007/s105890139578z.
Nasrin MohabbatiKalejahi, Hossein Akbaripour and Ellips Masehian, Basic and Hybrid Imperialist Competitive Algorithms for Solving the Nonattacking and Nondominating n Queens Problems, Studies in Computational Intelligence Volume 577, 2015, pp 7996. DOI 10.1007/9783319112718_6.
J. Pope and D. Sonnier, A linear solution to the nQueens problem using vector spaces, Journal of Computing Sciences in Colleges, Volume 29 Issue 5, May 2014 Pages 7783.
T. B. Preußer and M. R. Engelhardt, Putting Queens in Carry Chains, No. 27, 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.)
Thomas B. Preußer, Bernd Nägel and Rainer G. Spallek, Putting Queens in Carry Chains, Slides, HIPEAC WRC'09.
E. M. Reingold, Letter to N. J. A. Sloane, Dec 27 1973
I. Rivin, I. Vardi and P. Zimmermann, The nqueens problem, Amer. Math. Monthly, 101 (1994), 629639.
Michael Simkin, The number of nqueens configurations, arXiv:2107.13460 [math.CO], 2021.
Wenxi Wang, Muhammad Usman, Alyas Almaawi, Kaiyuan Wang, Kuldeep S. Meel and Sarfraz Khurshid, A Study of Symmetry Breaking Predicates and Model Counting, National University of Singapore (2020).
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set
Eric Weisstein's World of Mathematics, Queen Graph
Eric Weisstein's World of Mathematics, Queens Problem
M. B. Wells, Elements of Combinatorial Computing, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237240]
WikiMili, Eight queens puzzle, (2019).
Wikipedia, Eight Queens Puzzle
Cheng Zhang and Jianpeng Ma, Counting Solutions for the Nqueens and Latin Square Problems by Efficient Monte Carlo Simulations, arXiv:0808.4003 [condmat.statmech], 2008.


FORMULA

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


EXAMPLE

a(2) = a(3) = 0, since on 2 X 2 and 3 X 3 chessboards there are no solutions.
.
a(4) = 2:
++ ++
 . . Q .   . Q . . 
 Q . . .   . . . Q 
 . . . Q   Q . . . 
 . Q . .   . . Q . 
++ ++
a(5) = 10:
++ ++ ++ ++ ++
 . . . Q .   . . Q . .   . . . . Q   . . . Q .   . . . . Q 
 . Q . . .   . . . . Q   . . Q . .   Q . . . .   . Q . . . 
 . . . . Q   . Q . . .   Q . . . .   . . Q . .   . . . Q . 
 . . Q . .   . . . Q .   . . . Q .   . . . . Q   Q . . . . 
 Q . . . .   Q . . . .   . Q . . .   . Q . . .   . . Q . . 
++ ++ ++ ++ ++
++ ++ ++ ++ ++
 Q . . . .   . Q . . .   Q . . . .   . . Q . .   . Q . . . 
 . . . Q .   . . . . Q   . . Q . .   Q . . . .   . . . Q . 
 . Q . . .   . . Q . .   . . . . Q   . . . Q .   Q . . . . 
 . . . . Q   Q . . . .   . Q . . .   . Q . . .   . . Q . . 
 . . Q . .   . . . Q .   . . . Q .   . . . . Q   . . . . Q 
++ ++ ++ ++ ++
a(6) = 4:
++ ++ ++ ++
 . . . . Q .   . . . Q . .   . . Q . . .   . Q . . . . 
 . . Q . . .   Q . . . . .   . . . . . Q   . . . Q . . 
 Q . . . . .   . . . . Q .   . Q . . . .   . . . . . Q 
 . . . . . Q   . Q . . . .   . . . . Q .   Q . . . . . 
 . . . Q . .   . . . . . Q   Q . . . . .   . . Q . . . 
 . Q . . . .   . . Q . . .   . . . Q . .   . . . . Q . 
++ ++ ++ ++
 Hugo Pfoertner, Mar 17 2019


CROSSREFS

See A140393 for another version. Cf. A002562, A065256.
Cf. A036464 (2Q), A047659 (3Q), A061994 (4Q), A108792 (5Q), A176186 (6Q).
Cf. A099152, A006717, A051906, A319284 (backtrack trees).
Main diagonal of A348129.
Sequence in context: A189869 A054790 A140393 * A038216 A213603 A145911
Adjacent sequences: A000167 A000168 A000169 * A000171 A000172 A000173


KEYWORD

nonn,hard,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Terms for n=2123 computed by Sylvain PION (Sylvain.Pion(AT)sophia.inria.fr) and JoelYann FOURRE (JoelYann.Fourre(AT)ens.fr).
a(24) from Kenji KISE (kis(AT)is.uec.ac.jp), Sep 01 2004
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.
a(25) has been confirmed by the NTU 25Queen Project at National Taiwan University and Ming Chuan University, led by YuhPyng (Arping) Shieh, Jul 26 2005. This computation took 26613 days CPU time.
The NQueensatHome 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 NQueensathome version of the sequence.  N. J. A. Sloane, Jun 18 2008
It now appears that this sequence (A000170) is correct and A140393 is wrong.  N. J. A. Sloane, Nov 08 2008
Added a(26) as calculated by Queens(AT)TUD [http://queens.inf.tudresden.de/].  Thomas B. Preußer, Jul 11 2009
Added a(27) as calculated by the Q27 Project [https://github.com/preusser/q27].  Thomas B. Preußer, Sep 23 2016
a(0) = 1 prepended by Joerg Arndt, Sep 16 2018


STATUS

approved



