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
    Commented Sep 18, 2023 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$ Commented Sep 18, 2023 at 12:43
  • 3
    $\begingroup$ See this question for the 8 sets version. $\endgroup$ Commented Sep 18, 2023 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$ Commented Sep 18, 2023 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 you have read our privacy policy.

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