login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000170 Number of ways of placing n nonattacking queens on n X n board.
(Formerly M1958 N0775)
48
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

REFERENCES

J. R. Bitner and E. M. Reingold, Backtrack programming techniques, Commun. ACM, 18 (1975), 651-656.

J. Freeman, A neural network solution to the n-queens problem, The Mathematica J., 3 (No. 3, 1993), 52-56.

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

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.

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)

E. Masehian, H. Akbaripour, N. Mohabbati-Kalejahi, Landscape analysis and efficient metaheuristics for solving the n-queens problem, Computational Optimization and Applications, 2013; DOI 10.1007/s10589-013-9578-z.

J. Pope, D. Sonnier, A linear solution to the n-Queens problem using vector spaces, Journal of Computing Sciences in Colleges, Volume 29 Issue 5, May 2014 Pages 77-83.

M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, 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. 91-94 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=1..26.

Amazing Mathematical Object Factory, Information on the n Queens problem

Jordan Bell, Brett Stevens, A survey of known results and research areas for n-queens, Discrete Mathematics, Volume 309, Issue 1, 6 January 2009, Pages 1-31.

D. Bill, Durango Bill's The N-Queens Problem

W. Kosters, n-Queens bibliography

V. Kotesovec, Non-attacking chess pieces, 6ed

E. Masehian, H. Akbaripour, N. Mohabbati-Kalejahi, Solving the n Queens Problem using a Tuned Hybrid Imperialist Competitive Algorithm, 2013;

Bernd Nägel, Thomas B. Preußer, Rainer G. Spallek, Queens(AT)TUD project website.

I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), 629-639.

Eric Weisstein's World of Mathematics, Queens Problem

Cheng Zhang, Jianpeng Ma, Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations, 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) * ln(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.

CROSSREFS

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

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

Cf. A099152, A006717, A051906.

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=21-23 computed by Sylvain PION (Sylvain.Pion(AT)sophia.inria.fr) and Joel-Yann FOURRE (Joel-Yann.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 Yuh-Pyng (Arping) Shieh, Jul 26 2005. This computation took 26613 days CPU time.

Some of the links may be broken. I would appreciate receiving updates to them. - N. J. A. Sloane, May 01 2006

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

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.tu-dresden.de/]. Thomas B. Preusser (thomas.preusser(AT)tu-dresden.de), Jul 11 2009

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified November 23 22:48 EST 2014. Contains 249866 sequences.