6
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

enter image description here

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

enter image description here

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:
enter image description here

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:
enter image description here

...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:
enter image description here

$\endgroup$
1
$\begingroup$

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

9x9 and 10x10

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.

11x11 and 12x12

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.
16x16 and 18x18

$\endgroup$
0
$\begingroup$

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.

$\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.