7
$\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$
  • 2
    $\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
7
$\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$
1
$\begingroup$

I believe I have obtained better results than those posted previously:

I can place 4+4+8 queens on a 8x8, sorry for the basic formatting:

..22....
..22....
......33
.......3
....3...
11......
11......
....3333
I can also do 4+5+6 on a 8x8, which beats 4+5+5 ;)
..11...1
..1....1
.......1
........
33......
33......
....222.
.....22.

And for the bonus question:

I can place 8+8+11 on 11x11:

...222.....
...222.....
...22......
.........11
..........1
...........
.33........
333........
333........
......1111.
.......1111

$\endgroup$
  • 1
    $\begingroup$ Poker-wise, 4+5+5 beats 4+4+8; that's an interesting solution nonetheless. Your "9+9+9 on 11x11" got me all excited but unfortunately it seems wrong: the lower-right 1 diagonally attacks the upper-left 2. $\endgroup$ – Quuxplusone Oct 10 at 4:27
  • $\begingroup$ @Quuxplusone ah you are right. I had a bug in my program, thank you for spotting it! I can now do 8+8+11 on 11x11, so I have updated the answer. $\endgroup$ – Dmitry Kamenetsky Oct 10 at 4:58
  • 1
    $\begingroup$ Any chance you could share your program and/or contact me offline with any further improvements you find to the data table in this post? quuxplusone.github.io/blog/2019/01/24/… $\endgroup$ – Quuxplusone Oct 10 at 14:27
  • 1
    $\begingroup$ Very cool! I see that you posted solutions for c=2 in oeis.org/A250000/a250000_2.txt. It might be useful to post a similar file for c=3 on oeis.org/A328283. I've made a new blog post based on your program for c>=4: quuxplusone.github.io/blog/2019/10/18/… $\endgroup$ – Quuxplusone Oct 19 at 5:13
  • 1
    $\begingroup$ @Quuxplusone actually the solutions for c=3 are already there in oeis.org/A328283. Nice blog post! I am glad that someone is using my program for greater good. I was thinking of adding an OEIS entry for c=4 and linking to the current question, but I found c=4 rather boring - simply 4 armies that are completely symmetrical. Now c=5 is quite a bit more interesting... $\endgroup$ – Dmitry Kamenetsky Oct 19 at 5:56

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.