Discrete Peaceful Encampments

Over the past couple of days I’ve posted variations on “Peaceful Encampments” as puzzles on StackExchange, to try to drum up some interest in them. I’ve learned that puzzlers greatly prefer discrete puzzles (queens on a chessboard) over continuous puzzles (such as the original “Peaceful Encampments” as seen on this blog): my discrete puzzles have gotten quick and accurate answers, whereas my original continuous version is languishing.

The other day:

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

Today, player three enters the game!:

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).


I’ve wrote a C++ program to brute-force the maximum number of queens that can be placed peacefully on an NxN chessboard in the 2-army and 3-army cases. Much of the search space can be short-circuited, similarly to my meta-sudoku brute-forcer as seen on this blog (October 2018).

For two armies, the sequence of solutions is OEIS A250000:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(n) 0 0 1 2 4 5 7 9 12 14 17 21 24 28 32

(That is, on a 4x4 chessboard you can fit peacefully 2 white and 2 black queens; on a 5x5 chessboard you can fit peacefully 4 white and 4 black queens; and so on.)

For three armies, the sequence is not found in the OEIS.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(n) 0 0 0 1 1 2 3 4 5 7* 8* 10* 12* 12* 12*

(That is, on a 7x7 chessboard you can fit peacefully 3 white, 3 black, and 3 red queens; on an 8x8 chessboard you can fit peacefully 4 white, 4 black, and 4 red queens; and so on.)

Numbers with asterisks are my best solutions but not necessarily the best possible.

Here are my solutions, for the record:

4x4: 2 white, 1 black, 1 red (verified best)

.W..
...W
B...
..R.

5x5: 4 white, 2 black, 1 red (verified best)

WW...
...BB
.W...
W....
..R..

6x6: 3 white, 3 black, 2 red (verified best)

W.....
..B..B
.....B
......
WW....
...RR.

7x7: 4 white, 4 black, 3 red (verified best)

..WW...
..W....
......R
....W..
BB.....
BB.....
.....RR

8x8: 6 white, 5 black, 4 red (verified best)

..RR....
..RR....
......WW
.......W
.B......
BB......
BB......
.....WWW

9x9: 7 white, 6 black, 5 red (verified best)

..RRR....
..RR.....
.......BB
........B
.W.......
WW.......
WW.......
WW.......
......BBB

10x10: 8 white, 7 black, 7 red

...RR.....
...RRR....
...RR.....
........BB
.........B
..........
.WW.......
WWW.......
WWW.......
......BBBB

11x11: 9 white, 8 black, 8 red

...WWWW....
...WWW.....
..........R
..........R
......WW...
..B........
.BB........
BBB........
BB.........
........RRR
........RRR

12x12: 11 white, 10 black, 10 red

...RR.......
...RRR......
...RRR......
...RR.......
.........BBB
..........BB
...........B
.WW.........
WWW.........
WWW.........
WWW.........
.......BBBB.

13x13: 13 white, 12 black, 12 red

...RR........
...RRR.......
...RRRR......
...RRR.......
.........WWWW
..........WWW
...........WW
..B..........
.BB..........
BBB..........
BBB..........
BBB..........
........WWWW.

Notice the similarity between my conjectured 9x9, 12x12, and 13x13 solutions and my conjectured solution to the continuous “Peaceful Encampments” puzzle for three armies:

Three encampments of size 0.0718 each
Posted 2019-01-24