5
$\begingroup$

Here's a variation of Discrete Peaceful Encampments: 9 queens on a chessboard (which itself is a variation of Peaceful Encampments).

You have 4 white queens, 4 black queens, and 4 red queens. Place all these pieces onto a normal 8x8 chessboard in such a way that no white queen threatens a black queen, no black queen threatens a red queen, and no red queen threatens a white queen (nor vice versa).

Can you find a way to place more than 4 queens of each color "peacefully" on an 8x8 chessboard?

$\endgroup$
  • 1
    $\begingroup$ Bonus puzzle: If you have 8 queens of each of the three colors, how big a checkerboard do you need, in order to place them all peacefully? 12x12? 11x11? Smaller? $\endgroup$ – Quuxplusone Jan 24 at 16:59
  • $\begingroup$ No solution in $8+8+8$ on $10\times10$. See updated answer for $11\times11$ $\endgroup$ – Daniel Mathias Jan 26 at 19:19
6
$\begingroup$

Ok, I'ma call it.

There's no way to get more than 4 of every colour. Also, there is no simple way to prove this.

This is the most efficient way to do it:

enter image description here

Notice how

There's room for all kinds of shenanigans: You can add
* a white queen to e1 or a2
* a red queen to g2 or h7, and
* a black queen to e7, or
* any queen to g7, if you move a1 to a2 first
Annoyingly, adding any two colours always excludes every option of adding the third colour, no matter how much you shuffle the pieces around.

This way you can get

any two colours to 5, but not all. Also, you could get white to 5 (e1) and red to 6 (g2, g7), but black still stays at 4, so you get a 4-5-6 solution.

In addition to all that:

There's so much wiggle room in the above diagram, and you can get so very very close to a 5-5-5, that any simple impossibility proof (like "there aren't enough diagonals on the chess board") is not going to work.

This all is a result of feeding this problem into a highly sophisticated self learning neural network *, making it start from random (and later self-selected) positions, where every improvement path always led to this position, or one of its descendants, showing that this position is at least a local optimum.

*my brain

Now all that is needed is

a) a brute force solution proving that this is indeed the optimum, or
b) a 5-5-5 solution, or a simple proof of its impossibility.

If anyone can provide case b, I'll happily buy that person a beer, after a solid stint of banging my head against a wall.

$\endgroup$
  • $\begingroup$ A brute force solution shouldn't be too difficult $\endgroup$ – Daniel Mathias Jan 25 at 2:34
  • 1
    $\begingroup$ I have written a brute-force solver and confirm that you've found the optimum for an 8x8 grid. Unfortunately the solver is pretty complicated (in order to short-circuit parts of the search space) and so it's not what I would call a "simple proof." Plus, it takes about three minutes to run for 8x8, and is basically unusable as any kind of "proof" for 9x9 and higher. $\endgroup$ – Quuxplusone Jan 25 at 21:45
  • 1
    $\begingroup$ @Quuxplusone I too have written a solver, also confirming that there is no solutions with 10+10 or 5+5+5 on and 8x8 board. The run time for this is just a few seconds in an online debugging environment. I intend to modify it for the 'bonus puzzle' and for your 4-colors puzzle. If you are interested, the program is written in C. $\endgroup$ – Daniel Mathias Jan 26 at 0:32
  • $\begingroup$ @DanielMathias: I would be very interested to see it! Mine is (currently) at github.com/Quuxplusone/MetaSudoku/blob/master/… . $\endgroup$ – Quuxplusone Jan 26 at 0:40
  • 1
    $\begingroup$ @Quuxplusone Link here It is an uncommented work in progress. Any changes I save will be reflected, as the link opens my source as 'read-only' $\endgroup$ – Daniel Mathias Jan 26 at 0:50
3
$\begingroup$

Well, I can do 4+4+4:

 0 0 . . . . . .
 0 0 . . . . . .
 . . . . . . 1 1
 . . . . . . 1 1
 . . 2 . . . . .
 . . 2 . . . . .
 . . . . . . . .
 . . . . 2 2 . .

$\endgroup$
3
$\begingroup$

5+5+4 and 6+5+4, but no 5+5+5

The orange piece can be any color.
queens

for the bonus:

One of the yellow square can the 9th queen of appropriate color, this then has $9+9+8$ on an $11\times11$ board.
enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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