Discrete Peaceful Encampments: Player 4 has entered the game!

Question

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?

Answer 1

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:

Answer 2

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.

Answer 3

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.