# 8-queen puzzle on its head

You have 64 chess queens which come in 8 colors, with 8 queens per color. The goal is fill a chessboard with these queens so that any two queens of the same color cannot attack each other, even when allowed to move through differently colored queens. This means no two similarly colored queens may share a rank, file or diagonal.

In other words, can you fill a chessboard with 8 disjoint solutions to the classic Eight Queens puzzle?

What about with $n^2$ queens on an $n\times n$ board?

It is not possible on an 8x8 board.

The eight queens of each colour have to form a solution to the standard eight queens problem. There are only 12 such patterns (plus their rotations/reflections). We need both main diagonals to contain one queen of each colour, but only six of the 8-queen patterns have queens on both main diagonals. Unfortunately all six of those patterns also use up a square diagonally adjacent to a corner. There are only four such squares, but we would need to combine eight of those patterns to form a full solution.

On my puzzle website there is an old puzzle called Hoo-Doo which is essentially this same puzzle.

Some other board sizes:

A 7x7 solution:

1 2 3 4 5 6 7
6 7 1 2 3 4 5
4 5 6 7 1 2 3
2 3 4 5 6 7 1
7 1 2 3 4 5 6
5 6 7 1 2 3 4
3 4 5 6 7 1 2

A 5x5 solution:
1 2 3 4 5
4 5 1 2 3
2 3 4 5 1
5 1 2 3 4
3 4 5 1 2

There is no solution for smaller boards or for 6x6.
If $n$ is coprime to 6, then you can make a solution for the $n\times n$ board similar to the two solutions above. Each row is the row above cyclically shifted right two steps. I suspect the other board sizes have no solution, but have not been able to prove that.

• I'm pretty sure there's a solution for n=1 Oct 11 '16 at 8:47
• @Kruga It's a solution, but I am talking about boards bigger than 1x1. Oct 12 '16 at 12:52
• You say it's not possible on an 8x8 board, but the definition for coprime is if 2 numbers only share one factor (that being 1), and 8 is coprime to 6, so therefore, show me a solution of the puzzle. Oct 26 '16 at 18:30
• @GarrisonPendergrass 8 and 6 are not coprime, as they both have a factor 2. Oct 27 '16 at 12:28
• Oh right my bad. Oct 27 '16 at 15:02

Here is a a demonstration.

It is not possible

Take the following board:

It is a solution for castles, but not queens. (If queens couldn't move diagonally, this would be an acceptable solution)

So to fix the diagonal problems we can switch some of the queens. But if you switch enough queens you will result in a horizontal or vertical error, hence it is impossible

• I don't think your reasoning is valid; you can switch any two rows or columns and the board remains a solution for rooks. Oct 11 '16 at 15:18
• @2012rcampion my point is you couldn't switch it so it works Oct 11 '16 at 15:21
• But why not? You're assuming that there is no solution in order to prove there is no solution (begging the question). Oct 11 '16 at 15:25
• Even if the shallow argument "you couldn't switch" would work, you also assume here that there is a unique starting-point matrix. But that is also not the case. Do you have the disciplined badge, by the way? Oct 11 '16 at 17:42
• @Matsmath, I do Oct 11 '16 at 17:45