|
%I M1958 N0775 #256 Dec 22 2023 11:12:10
%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
%C Number of permutations of [1...n] such that |p(j)-p(i)| != j-i for i<j. - _Xiangyu Chen_, Dec 24 2020
%C 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
%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 W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed., New York, Dover, 1987, pp. 166-172 (The Eight Queens Problem).
%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 and 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 Candida Bowtell and Peter Keevash, <a href="https://arxiv.org/abs/2109.08083">The n-queens problem</a>, arXiv:2109.08083 [math.CO] 2021.
%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 and 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 Matteo Fischetti and Domenico Salvagnin, <a href="https://arxiv.org/abs/1907.08246">Finding First and Most-Beautiful Queens by Integer Programming</a>, arXiv:1907.08246 [cs.DS], 2019.
%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 and 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 Eric Grigoryan, <a href="https://doi.org/10.13187/mai.2018.1.3">Investigation of the Regularities in the Formation of Solutions n-Queens Problem</a>, Modeling of Artificial Intelligence, 2018, 5(1), 3-21.
%H E. Grigoryan, <a href="https://arxiv.org/abs/1912.05935">Linear algorithm for solution n-Queens Completion problem</a>, arXiv:1912.05935 [cs.AI], 2019.
%H James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=jPcBU0Z2Hj8">The 8 Queen Problem</a>, Numberphile video (2015).
%H Michael Han, Tanya Khovanova, Ella Kim, Evin Liang, Miriam Lubashev, Oleg Polin, Vaibhav Rastogi, Benjamin Taycher, Ada Tsui and Cindy Wei, <a href="https://arxiv.org/abs/2109.01530">Fun with Latin Squares</a>, arXiv:2109.01530 [math.HO], 2021.
%H Kenji Kise, Takahiro Katagiri, Hiroki Honda and Toshitsugu Yuba, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.4098">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 D. E. Knuth, <a href="https://youtu.be/_cR9zDlvP88?t=3009">Donald Knuth's 24th Annual Christmas Lecture: Dancing Links</a>, Stanfordonline, Video published on YouTube, Dec 12, 2018.
%H W. Kosters, <a href="http://www.liacs.nl/~kosters/nqueens/index.html">n-Queens bibliography</a>
%H Vaclav Kotesovec, <a href="http://www.kotesovec.cz/books/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 Zur Luria, <a href="https://arxiv.org/abs/1705.05225">New bounds on the number of n-queens configurations</a>, arXiv:1705.05225 [math.CO], 2017.
%H Zur Luria, Michael Simkin, <a href="https://arxiv.org/abs/2105.11431">A lower bound for the n-queens problem</a>, arXiv:2105.11431 [math.CO], 2021.
%H E. Masehian, H. Akbaripour and 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 and 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 and 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 Ralph Morrison and Noah Speeter, <a href="https://arxiv.org/abs/2312.04686">The Gonality of Queen's Graphs</a>, arXiv:2312.04686 [math.CO], 2023.
%H Parth Nobel, Akshay Agrawal and Stephen Boyd, <a href="https://arxiv.org/abs/2112.03336">Computing tighter bounds on the n-queens constant via Newton’s method</a>, arXiv:2112.03336 [math.CO], 2021.
%H J. Pope and 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 and 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 and 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 Werner Florian Samayoa, Maria Liz Crespo, Sergio Carrato, Agustin Silva, and Andres Cicuttin, <a href="https://doi.org/10.21203/rs.3.rs-3278560/v1">HyperFPGA: An Experimental Testbed for Heterogeneous Supercomputing</a>, 2023.
%H Michael Simkin, <a href="https://arxiv.org/abs/2107.13460">The number of n-queens configurations</a>, arXiv:2107.13460 [math.CO], 2021.
%H Wenxi Wang, Muhammad Usman, Alyas Almaawi, Kaiyuan Wang, Kuldeep S. Meel and Sarfraz Khurshid, <a href="https://www.comp.nus.edu.sg/~meel/Papers/tacas20.pdf">A Study of Symmetry Breaking Predicates and Model Counting</a>, National University of Singapore (2020).
%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 WikiMili, <a href="https://wikimili.com/en/Eight_queens_puzzle">Eight queens puzzle</a>, (2019).
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Eight_queens_puzzle">Eight Queens Puzzle</a>
%H Cheng Zhang and 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
%F Lim_{n->infinity} a(n)^(1/n)/n = exp(-A359441) = 0.1431301... [Simkin 2021]. - _Vaclav Kotesovec_, Jan 01 2023
%e a(2) = a(3) = 0, since on 2 X 2 and 3 X 3 chessboards there are no solutions.
%e .
%e a(4) = 2:
%e +---------+ +---------+
%e | . . Q . | | . Q . . |
%e | Q . . . | | . . . Q |
%e | . . . Q | | Q . . . |
%e | . Q . . | | . . Q . |
%e +---------+ +---------+
%e a(5) = 10:
%e +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
%e | . . . Q . | | . . Q . . | | . . . . Q | | . . . Q . | | . . . . Q |
%e | . Q . . . | | . . . . Q | | . . Q . . | | Q . . . . | | . Q . . . |
%e | . . . . Q | | . Q . . . | | Q . . . . | | . . Q . . | | . . . Q . |
%e | . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | Q . . . . |
%e | Q . . . . | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
%e +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
%e +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
%e | Q . . . . | | . Q . . . | | Q . . . . | | . . Q . . | | . Q . . . |
%e | . . . Q . | | . . . . Q | | . . Q . . | | Q . . . . | | . . . Q . |
%e | . Q . . . | | . . Q . . | | . . . . Q | | . . . Q . | | Q . . . . |
%e | . . . . Q | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
%e | . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | . . . . Q |
%e +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
%e a(6) = 4:
%e +-------------+ +-------------+ +-------------+ +-------------+
%e | . . . . Q . | | . . . Q . . | | . . Q . . . | | . Q . . . . |
%e | . . Q . . . | | Q . . . . . | | . . . . . Q | | . . . Q . . |
%e | Q . . . . . | | . . . . Q . | | . Q . . . . | | . . . . . Q |
%e | . . . . . Q | | . Q . . . . | | . . . . Q . | | Q . . . . . |
%e | . . . Q . . | | . . . . . Q | | Q . . . . . | | . . Q . . . |
%e | . Q . . . . | | . . Q . . . | | . . . Q . . | | . . . . Q . |
%e +-------------+ +-------------+ +-------------+ +-------------+
%e - _Hugo Pfoertner_, Mar 17 2019
%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).
%Y Main diagonal of A348129.
%K nonn,hard,nice
%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
| 