An [interesting question](https://puzzling.stackexchange.com/questions/22846/88/) 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?



$n$ groups of $n$ queens on a toroidal chessboard
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](http://ac.els-cdn.com/0097316574900764/1-s2.0-0097316574900764-main.pdf?_tid=09d920d2-6df8-11e5-a2ad-00000aacb35d&acdnat=1444334959_ce0a7035df79bbd9caf7a2917b5dad74) 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)


