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?
Asked
Active
Viewed 1,061 times
1
-
See your comment on your post https://puzzling.stackexchange.com/questions/94766/knights-attacking-exactly-three-knights – Florian F Sep 18 '23 at 12:39
-
1yeah I feel that this one is somewhat different. – Dmitry Kamenetsky Sep 18 '23 at 12:42
2 Answers
9
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}
RobPratt
- 13,685
- 1
- 29
- 56
6
The answer is
Yes.
Take any one of the well-known 8-queen solutions together with its horizontal or vertical mirror image.
loopy walt
- 21,184
- 33
- 95
-
1The next question is how many independent sets can you place? Can you place 8 sets? – Florian F Sep 18 '23 at 12:33
-
@FlorianF good question. I don't think 8 sets is possible, but more than 2 should be possible. Worth asking. – Dmitry Kamenetsky Sep 18 '23 at 12:43
-
3
-
1I 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). – Jeff Zeitlin Sep 18 '23 at 13:54