5
$\begingroup$

An interesting question came up in the Puzzling Stack Exchange a few days ago about "queen-connected sets". When trying to solve this problem, I came across an arrangement of five colours of queens that would not attack each other on a toroidal 5×5 chessboard, and discovered that 4 queens could be placed into two non-attacking groups but not four individual ones.

Let a queen number be a number $n$ where there exists an arrangement of $n$ colours of $n$ queens that are placed on an $n \times n$ chessboard, such that no queen can attack a queen of the same colour, including through broken diagonals.

5 is the smallest queen number, and the arrangement I found is the one where all of them are a knight's move away from each other:

1 2 3 4 5
3 4 5 1 2
5 1 2 3 4
2 3 4 5 1
4 5 1 2 3

I haven't come across a way to prove that 6 is not a queen number, although I suspect that's true. I also tried making an arrangement for 10 just now using the same method that I used for 5, but it didn't work:

1234567890
4567890123
7890123456
0123456789
3456789012
6789012345
9012345678
2345678901
5678901234
8901234567

If you notice, every queen attacks the next queen 5 squares right and 5 squares down. But I don't know if there is another arrangement that does work.

Is there any way to determine the set of queen numbers without going through every arrangement to verify that it solves the problem?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If the problem were about rooks, you would be talking about Latin squares, of which there is much literature. Queen problems on various boards have been considered. Try a web search and tell us what you find. Gerhard "Studying Boards Made Of Hexagons" Paseman, 2015.10.08 $\endgroup$
    – Gerhard Paseman
    Oct 8, 2015 at 18:20
  • 4
    $\begingroup$ The problem is equivalent if you just ask about 1 color, since positions of the remaining n-1 colors may be obtained by translation symmetry simply by shifting the pattern, as is readily apparent in your 5x5 example. $\endgroup$
    – user00000
    Oct 8, 2015 at 19:09
  • $\begingroup$ $6$ is not a queen number. To see this, just notice that you have to place some queen in the top square of the first column. You then have only three choices for the queen of the same color in the next column. Each of these three choices leads pretty quickly to a contradiction. $\endgroup$
    – Will Brian
    Oct 8, 2015 at 19:56

1 Answer 1

Reset to default
8
$\begingroup$

The "queen numbers" are precisely those numbers whose smallest prime factor is at least 5.

It is a theorem of Polya that

You can place n queens on an nxn toroidal board such that no two queens can attack each other if and only if the smallest prime factor of n is at least 5.

I couldn't find Polya's paper in English, but this paper of Chandra states the theorem above, and also solves some interesting multi-dimensional generalizations of your question.

To get from Polya's theorem to answering your question:

If n is a queen number, then looking at just one color I see that I have place n queens on an nxn toroidal board so that no two can attack each other. Conversely, if I have placed n queens on an nxn toroidal board in this way, then by shifting my solution n-1 times, I can find a way to place the other n-1 colors (this idea was given in a comment by user76105)

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.