7
$\begingroup$

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?

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ I'm pretty sure there's a solution for n=1 $\endgroup$ – Kruga Oct 11 '16 at 8:47
  • $\begingroup$ @Kruga It's a solution, but I am talking about boards bigger than 1x1. $\endgroup$ – garr890354839 Oct 12 '16 at 12:52
  • $\begingroup$ 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. $\endgroup$ – garr890354839 Oct 26 '16 at 18:30
  • 2
    $\begingroup$ @GarrisonPendergrass 8 and 6 are not coprime, as they both have a factor 2. $\endgroup$ – Jaap Scherphuis Oct 27 '16 at 12:28
  • $\begingroup$ Oh right my bad. $\endgroup$ – garr890354839 Oct 27 '16 at 15:02
2
$\begingroup$

Here is a a demonstration.

It is not possible

Take the following board:

enter image description here

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

$\endgroup$
  • $\begingroup$ I don't think your reasoning is valid; you can switch any two rows or columns and the board remains a solution for rooks. $\endgroup$ – 2012rcampion Oct 11 '16 at 15:18
  • $\begingroup$ @2012rcampion my point is you couldn't switch it so it works $\endgroup$ – Beastly Gerbil Oct 11 '16 at 15:21
  • 1
    $\begingroup$ But why not? You're assuming that there is no solution in order to prove there is no solution (begging the question). $\endgroup$ – 2012rcampion Oct 11 '16 at 15:25
  • 2
    $\begingroup$ 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? $\endgroup$ – Matsmath Oct 11 '16 at 17:42
  • $\begingroup$ @Matsmath, I do $\endgroup$ – Beastly Gerbil Oct 11 '16 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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