# Discrete Peaceful Encampments: Player 4 has entered the game!

Here's a variation of Discrete Peaceful Encampments: Player 3 has entered the game! (which itself is a variation of Peaceful Encampments).

You have 3 white queens, 3 black queens, 3 red queens, and 3 green queens. Place all these pieces onto a normal 8x8 chessboard in such a way that no queen threatens a queen of a different color.

Okay, that was easier than the previous variations, right? You can probably use the pattern you found to solve these problems as well:

Place 5 queens of each of four different colors onto a 10x10 checkerboard so that no queen threatens a queen of a different color.

Place 7 queens of each of four different colors onto a 12x12 checkerboard so that no queen threatens a queen of a different color.

Which leads to the real puzzle:

At what point does it become possible to place more than $$N-5$$ queens of each of four different colors peacefully onto an $$N\times N$$ checkerboard?

## 3 Answers

While I feel it could be, this may not be optimal. However it is, at least, an upper bound...

$$N=14$$.

I first note that it must be possible with:

$$N=25$$.
Since $$N-4=21=(6+5+4+3+2+1)$$
and $$\frac{N}{4}\ge 6$$
it follows that we can build a symmetric solution where each army occupies a right-isosceles-triangle of side $$6$$.

Like so (the green shading shows the locations under attack by army A):

...and the layout has $$4$$-fold rotational symmetry,
so rotating a quarter or half-turn, other armies are just like A.

...and then note that:

we can squeeze the same armies of $$21$$ onto a $$24 \times 24$$ board, by removing the central column & middle row:

and that we can

...remove the bottom-right soldier of army A (and equivalents), squeeze that into a $$23 \times 23$$ as above, then remove the outermost three rings of locations
...for four armies of $$14$$ on a $$17 \times 17$$ board:

Similarly

...remove the three bottom-right soldiers of army A (and equivalents) and squeeze to make armies of $$11$$ on a $$15 \times 15$$ board:

...and (thanks to Daniel Mathias!)

...remove the top-right soldier of army A (and equivalents) and squeeze to make armies of $$10$$ on a $$14 \times 14$$ board:

There exists no solution for $$4$$ armies of $$9$$ queens each on a $$13\times13$$ board, so Jonathan's $$10$$ on $$14$$ is the first with armies of $$N-4$$ queens.

Here are all of the distinct solutions for armies of $$4$$ queens on a $$9\times9$$ board and armies of $$5$$ queens on a $$10\times10$$ board. (Exception: any queen can be moved to the center square of the fourth 9x9 board.)

These are the only solutions for armies of $$6$$ queens on an $$11\times11$$ board. For the $$12\times12$$ and larger boards, the search was modified to find only rotationally symmetrical solutions.

Optimal solutions on $$16\times16$$ and $$18\times18$$ boards:

These solutions can be easily expanded to ever larger boards, with armies of $$18$$ queens on a $$19\times19$$ board and armies of $$20$$ queens on a $$20\times20$$ board. The claim that these are optimal is based on the fact that there were no centrally located queens in any solution on $$10\times10$$ or $$11\times11$$ boards. This suggests that your general solution for $$4$$ armies is itself optimal.

I haven’t completed my proof yet, but I believe from preliminary results:

12 is the lower bound. Whether 12 or 13 works is yet to be seen.