login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A168553 a(n) = 1 if it is possible to place n sets of n queens on an n X n chessboard with no two queens of the same set attacking each other. 0
1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Obviously this sequence must be a subset of the positive integers for which a single n-queens solution exists, which is all integers except 2 and 3. It is a proper subset, because e.g. there is a single-set solution for 4 X 4 or 8 X 8 but no n-set solution. George Polya showed that a doubly periodic solution for the n-queens problem exists if and only if n = 1 or 5 (mod 6). For years, due to this result, it was assumed that this defined the sequence, which would then have been an infinite repetition of 1,0,0,0,1,0. However, Patrick Hamlyn and Guenter Stertenbrink tried brute force on 12 X 12 and found 178 12-set solutions built from non-doubly-periodic sets. Thus the Polya condition only provides a lower bound, and the exact continuation of this sequence is an open research question.

REFERENCES

G. Polya, Uber die 'doppelt-periodischen' Losungen des n-Damen-Problems. In Mathematische Unterhaltungen und Spiele, W. Ahrens, Ed., Teubner, Leipzig, 1918, pp. 364-374.

LINKS

Table of n, a(n) for n=1..12.

Wolfram Research, The 12x12 Queens Problem

EXAMPLE

For n=1 a single queen is a solution. For n=2 or 3 there is no single-set solution. For n=4, there are 2 single-set solutions, and they can both fit on the board together, but these are insufficient to make a 4-set solution. For n=5, there is a doubly-periodic single-set solution by Polya's construction, which can be tiled to make a 5-set solution

CROSSREFS

A000170 gives the number of single-set solutions. A007705 gives the number of Polya-style doubly-periodic single-set solutions (with even n omitted since they are all 0).

Sequence in context: A267056 A089024 A232991 * A267636 A267841 A309850

Adjacent sequences:  A168550 A168551 A168552 * A168554 A168555 A168556

KEYWORD

hard,more,nonn

AUTHOR

Howard A. Landman, Nov 29 2009

STATUS

approved

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 September 16 05:49 EDT 2021. Contains 347469 sequences. (Running on oeis4.)