1
$\begingroup$

Can you place 8 white queens and 8 black queens on an 8x8 grid, such that no two queens of the same colour occupy the same row, column or diagonal?

$\endgroup$
2

2 Answers 2

6
$\begingroup$

The answer is

Yes.

Take any one of the well-known 8-queen solutions together with its horizontal or vertical mirror image.

$\endgroup$
4
  • 1
    $\begingroup$ The next question is how many independent sets can you place? Can you place 8 sets? $\endgroup$
    – Florian F
    Sep 18 at 12:33
  • $\begingroup$ @FlorianF good question. I don't think 8 sets is possible, but more than 2 should be possible. Worth asking. $\endgroup$ Sep 18 at 12:43
  • 3
    $\begingroup$ See this question for the 8 sets version. $\endgroup$ Sep 18 at 12:48
  • 1
    $\begingroup$ I suspect that as long as a 90-degree rotation doesn't end up with two queens of opposite colors on the same square, you can use 90-degree rotations as well. Also 180-degree rotations (as opposed to reflections). $\endgroup$ Sep 18 at 13:54
9
$\begingroup$

For the question of maximizing the number of sets of $8$ queens, define a graph with a node for each of the $92$ solutions for $8$ queens and an edge for each pair of solutions that share a cell. Now find a maximum independent set in this graph. The maximum turns out to be

$6$, achieved as follows: \begin{matrix}&6&5&4&.&3&2&.&1\\&.&1&3&2&4&5&6&.\\&5&4&.&6&1&.&2&3\\&2&.&1&3&.&6&5&4\\&1&.&2&5&.&4&3&6\\&3&6&.&4&2&.&1&5\\&.&2&5&1&6&3&4&.\\&4&3&6&.&5&1&.&2\\\end{matrix}

$\endgroup$

Your Answer

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

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