|
| |
|
|
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
|
|
|
|
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).
|
|
|
KEYWORD
|
hard,more,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
