Discrete Peaceful Encampments, with tables

Previously on this blog: “Discrete Peaceful Encampments” (2019-01-24).

Dmitry Kamenetsky has written a Java program that heuristically finds solutions (not necessarily best-possible solutions) to the “peaceable coexisting queens” problem, for any size board and any number of colors .

Here’s a table of the largest integers such that armies of queens each can all be encamped peaceably on a board.

k=       1  2  3  4  5  6  ...
      .
n=1   .  1  0
n=2   .  4  0  0
n=3      9  1  0  0
n=4     16  2  1  1  0
n=5     25  4  1  1  1  0
n=6     36  5  2  2  1  1  0
n=7     49  7  3  2  1  1  1  0
n=8     64  9  4  3  2  1  1  1  0
n=9     81 12  5  4  2  2  1  1  1  0
n=10   100 14  7  5  4  2  1  1  1  1  0
n=11   121 17  8  6  4  2  2  1  1  1  1  0
n=12   144 21 10  7  4  3  2  2  1  1  1  1  0
n=13   169 24 12  8  5  4  2  2  1  1  1  1  1  0
n=14   196 28 14 10  6  4  4  2  2  1  1  1  1  1  0
n=15   225 32 16 11  9  4  4  2  2  2  1  1  1  1  1  0
n=16   256 37 18 13  9  5  4  3  2  2  1  1  1  1  1  1  0
n=17   289 42 20 14  9  5  4  3  2  2  2  1  1  1  1  1  1  0
n=18   324 47 23 16 11  6  4  3  3  2  2  2  1  1  1  1  1  1  0
n=19   361 52 25 18 12  7  5  4  3  2  2  2  1  1  1  1  1  1  1  0
n=20   400 58 28 20 16  8  6  4  3  3  2  2  2  1  1  1  1  1  1  1  0

Column of this table is OEIS A250000. Column of this table is OEIS A328283. Diagonal represents the existence of solutions to the -queens problem (that is, it’s 1 for all except 2 and 3).

These numbers are merely my best lower bounds based on Dmitry Kamenetsky’s program; any numbers not already listed in OEIS should not be taken as gospel.

The clever solution for is just the 2x2 tessellation of the solution to ; and likewise the clever solution to .


Here’s a table of the largest integers such that armies of queens each, plus one army of queens, can all be encamped peaceably on a board. By definition, .

k=       1  2  3  4  5  6  ...
      .
n=1   .  1  0
n=2   .  4  0  0
n=3      9  2  0  0
n=4     16  3  3  1  0
n=5     25  4  7  3  1  0
n=6     36  6  6  2  4  1  0
n=7     49  7  6  4  7  4  1  0
n=8     64 10  8  4  4  7  4  1  0
n=9     81 12  9  5  9  2  7  4  1  0
n=10   100 15  8  5  4  5 12  7  4  1  0
n=11   121 19 11  7  6  8  3 12  9  4  1  0
n=12   144 21 11  7 10  4  7  2 12  8  4  1  0
n=13   169 25 12  9  9  4 10  4 18 13  8  4  1  0
n=14   196 29 14 10 10  6  4  8  3 18 12  7  4  1  0
n=15   225 34 17 12  9  9  6 13  6  2 18 12  8  4  1  0
n=16   256 37 19 13 16 10  5  4 11  5 24 17 12  7  4  1  0
n=17   289 42 24 15 17 11  7  5 10  8  3 20 15 10  7  4  1  0
n=18   324 48 24 16 13 10  9  7  4 10  5  2 20 15 10  7  4  1  0
n=19   361 53 28 19 13 14  6  5  6 13  7  4 26 19 14 10  6  4  1  0
n=20   400 59 31 20 16 10  9  8  8  3 10  5  3 26 20 15 10  7  4  1  0

Row c=2 of this table is OEIS A308632.

Again, these numbers are merely my best guesses based on Dmitry Kamenetsky’s program; they should not be taken as gospel. They are neither upper bounds nor lower bounds! For example, on a 12x12 board you can definitely encamp 10+4+4+4+4 queens, so 4 is a hard lower bound for ; but might be either greater than 10 or (if it turns out that ) less than 10.

Also notice that for example on an 11x11 board you can encamp 8+8+11 queens or 8+9+10 queens, but not (as far as I know) 8+9+11. So and , but it would be reasonable to imagine defining some related sequence such that .


I have ported Dmitry’s Java program to C++14 and made it compute the entire triangle (that is, compute all the entries in parallel and periodically write its best results to a file on disk). A complete listing of its “best” solutions is here, and the C++14 source code itself is here.

Posted 2019-10-18