What is the most number of black and white queens that you can place on a standard 8x8 chess board, such that each queen attacks exactly one opponent queen?
2$\begingroup$ Depending on the allowed rules, this may be a duplicate of: puzzling.stackexchange.com/questions/2799/… $\endgroup$– Joel RondeauMar 2, 2020 at 14:45
2$\begingroup$ Sorry all for the confusion. I have now clarified the question. $\endgroup$– Dmitry KamenetskyMar 2, 2020 at 23:33
3$\begingroup$ Someone might be able to beat it. I have not been able to prove my answer is a maximum. $\endgroup$– Joel RondeauMar 2, 2020 at 23:47
3$\begingroup$ @Joel Done. (See below) $\endgroup$– Daniel MathiasMar 3, 2020 at 11:36
1$\begingroup$ @CSM, I don't think you can have all 42 black queens attacking that lone white queen, let alone so that the white one would only attack one of the black ones. $\endgroup$– ilkkachuMar 4, 2020 at 21:15
1$\begingroup$ Whoa, nice density, I guess this is the maximum if you can't add other pieces than queens. It is easy to reach higher density on a 3x3 board, but I can't think of a way to even get 4x4 board with one extra queen to the pairs. $\endgroup$ Mar 3, 2020 at 12:32
1$\begingroup$ Very nice Daniel! This will be hard to top. $\endgroup$ Mar 3, 2020 at 12:43
6$\begingroup$ This answer is beautiful in its simplicity, and I'm annoyed at myself for not trying something similar. $\endgroup$ Mar 3, 2020 at 14:52
I saw no implications that we aren't going by standard chess rules.
Given that we only allow queens to attack the opposing color I propose:
3$\begingroup$ This is the only form of this question that isn't part of the linked question, and is very interesting. $\endgroup$ Mar 2, 2020 at 16:24
Following @Konstantin Pfennig's answer, using black and white queens, and squeezing in more, I have:
26 queens, 13 to a side.I started out with 12 to a side, symmetrically, but when I added the queens on D1 and D2, I needed to move the A5 queen to A7. I was hoping for a 14th white queen on E7, but couldn't fit it in.
$\begingroup$ when you mirror the left half to the right you could get that 14th pair in there and also restore symmetry. really neat set up either way $\endgroup$ Mar 3, 2020 at 8:24
$\begingroup$ never mind my last statement. i just realized why that doesn't work $\endgroup$ Mar 3, 2020 at 8:44
You can only place at most
If each queen attacks exactly one other queen, then the queen being attacked is also attacking the original queen. So the queens have to come in pairs. Now, the board only has 8 rows and 8 columns. For each pair of queens, they will necessarily take either 2 rows and 1 column, 2 columns and 1 row, or 2 rows and 2 columns if they are attacking each other on the diagonal.
You have probably guessed that having them attack on the diagonal is not optimal. With these constraints, you can place at most 5 pairs. Any more and you will need either more than 8 rows or more than 8 columns.
Here is one solution:
1$\begingroup$ What if you have queens of the same color as blockers? $\endgroup$ Mar 3, 2020 at 23:07
With only queens on the board, I agree with Amorydai that the maximum is 10.
Since it was not stated whether only queens can be placed on the board, I believe up to 26 can be placed.
It is possible to have higher queen density with blocking pieces.
I managed 19 pairs, 38 queens using pretty simple 3x3 tile that achieves highest density without blockers - but blockers must be added to replicate the pattern.
This approach uses the highest density 3x3 tile seen in top-left corner (for 3x3 there is no need for blocking pieces). The last two rows and columns are simple 1/2 density that is simple enough to achieve with blockers.
It may be possible to do even better, I am not too satisfied with the last 2 rows and columns of the solution above.
2xN tiles are obvious to be limited to mere 1/2 density with matching queens, so don't bother wiggling those queens on last two rows/columns. I also haven't found a good 4x4 tile with higher density and I suspect it does not exist. But it may be possible to use 5x5, 3x5 and 3x3 tiles to achieve high resulting density and place 20 pairs on the chessboard. But checking all reasonable options on the 5x5 is a huge pain.
2$\begingroup$ for the nice images you can use lichess.org $\endgroup$ Mar 4, 2020 at 9:41
$\begingroup$ @KonstantinPfennig Thanks for the edit, hopefully I will remember this the next time similar question comes up. $\endgroup$ Mar 4, 2020 at 10:43
2$\begingroup$ Twenty $\endgroup$ Mar 4, 2020 at 13:41
2$\begingroup$ @DanielMathias Great job. Post it along your existing solution. $\endgroup$ Mar 4, 2020 at 19:33
I wrote a hill-climbing program that finds solutions. It turns out that there can be other solutions with the optimal number of queens, some even non-symmetrical:
I believe it's 8, and here is a possible solution. Every pair of attacking queens must exclusively occupy at least 1 row and 2 columns or 2 rows and 1 column, making any number greater than 8 impossible because aren't enough rows or columns to contain >4 pairs.
1$\begingroup$ This works if every pair uses a row (2 cols) or if every pair uses 1 column (2 rows). But if one pair is on a row and another pair is on a column then you have only used 3 rows and 3 columns for 4 queens. $\endgroup$– IanF1Mar 2, 2020 at 6:02
1$\begingroup$ Yep, you're totally right! I don't know why I didn't think of that... $\endgroup$ Mar 2, 2020 at 6:03
1$\begingroup$ I only saw it when trying to work out how Amorydai's answer contradicted yours :) $\endgroup$– IanF1Mar 2, 2020 at 6:19