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?
$\begingroup$
$\endgroup$
2
asked Sep 18 at 11:43
-
$\begingroup$ See your comment on your post puzzling.stackexchange.com/questions/94766/… $\endgroup$– Florian FSep 18 at 12:39
-
1$\begingroup$ yeah I feel that this one is somewhat different. $\endgroup$– Dmitry KamenetskySep 18 at 12:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
The answer is
Yes.
Take any one of the well-known 8-queen solutions together with its horizontal or vertical mirror image.
-
1$\begingroup$ The next question is how many independent sets can you place? Can you place 8 sets? $\endgroup$ 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
-
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
$\begingroup$
$\endgroup$
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}
