

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 nqueens solution exists, which is all integers except 2 and 3. It is a proper subset, because e.g. there is a singleset solution for 4 X 4 or 8 X 8 but no nset solution. George Polya showed that a doubly periodic solution for the nqueens 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 12set solutions built from nondoublyperiodic 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 'doppeltperiodischen' Losungen des nDamenProblems. In Mathematische Unterhaltungen und Spiele, W. Ahrens, Ed., Teubner, Leipzig, 1918, pp. 364374.


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 singleset solution. For n=4, there are 2 singleset solutions, and they can both fit on the board together, but these are insufficient to make a 4set solution. For n=5, there is a doublyperiodic singleset solution by Polya's construction, which can be tiled to make a 5set solution


CROSSREFS

A000170 gives the number of singleset solutions. A007705 gives the number of Polyastyle doublyperiodic singleset 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



