A250000 Peaceable coexisting armies of queens: the maximum number m such that m white queens and m black queens can coexist on an n X n chessboard without attacking each other.

0, 0, 1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24, 28, 32

Offset: 1

Author

Don Knuth, Aug 01 2014

Keywords

• nonn
• nice
• more

Comments

Comments from N. J. A. Sloane, May 22 2019: (Start)

The earliest reference known for this problem is Ainley (1977) - see reference and excerpts below. He found constructions for n <= 30 which have never been surpassed (except for n=27 - see Knuth's comment below), and he gave a general construction (the 4-pentagon or "4-blob" construction) which achieves a lower bound of 7*n^2/48.

Most of the results described in the examples and comments below (with the exception of the optimality proofs and the enumeration of different solutions) are rediscoveries of Ainley's work.

Ainley's values for n = 1 through 30 are 0, 0, 1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24, 28, 32, 37, 42, 47, 52, 58, 64, 70, 77, 84, 91, 98, 105, 114, 122, 131. (End)

Sequence A260680 counts the inequivalent configurations or "solutions" corresponding to the maximum number a(n) of queens of each color. Two solutions are regarded as equivalent if one can be obtained from the other by rotations, reflections, or interchanging the colors (a group of order 16).

For the number of inequivalent solutions see A260680.

From Bob Selcoe, Feb 09 2015: (Start)

For n = 4m, a generalized quasi-symmetric pattern of queen arrangements exists showing that a(n) >= ceiling((n+4)(n-2)/8) + floor((n-4)^2/64) == (m+1)(2m-1) + A002620(m-1).

For n = 4m-1, a slightly different pattern exists showing that a(n) >= m(2m-1) + A002620(m).

Both patterns are difficult to describe easily: as m increases, each depends on slight variations to standard arrangements of opposing queens in "blocks" on opposite corners of the chessboard, plus an additional block arrangement which is "forced" by virtue of the corner blocks. See below for examples of boards for n = {12,16,20,24} that show the pattern for n = 4m.

For all n >= 16, a(n) > ceiling(9n^2/64), which is the best asymptotic lower bound presently known.

It is likely that similar "block" patterns exist for n = {4m+1, 4m+2}.

(End)

Comments from Benoit Jubin, Feb 24 2015: (Start)

By modifying the Pratt-Selcoe configuration, I improved the best known lower bound from a(n) > (9/4)*(n/4)^2 to a(n) > (7/3)*(n/4)^2.

I have been sloppy with side effects, but to be on the safe side, let's say a(n) > (7/3)*(floor(n/4))^2 - (3+8*sqrt(2)/3)*ceiling(n/4), where the coefficient 3+8*sqrt(2)/3 is a perimeter that you can compute from the following description.

The configuration in the limit n = infinity is as follows: denoting by x,y in [0,1] the coordinates on the chessboard, the queens of one color are in the two regions x < 1/4, y < 1/2, x < y < x+1/3 and 1/2 < x < 3/4, y < x-1/3, y < 1-x and the queens of the other color are obtained by central symmetry.

As you can guess, I obtained these coefficients by equalizing the lengths of the "opposite" boundaries of the armies (this already improves (by 1) on the "Board 4" example of the webpage).

Using an easy upper bound, one has asymptotically

(2+1/3)*(n/4)^2 < a(n) < 4*(n/4)^2.

Nov 20 2018: Benoit Jubin explained how his upper bound was obtained, as follows:

Let's replace the queens with "amicable rooks". Say white rooks together control a columns and b rows, and the number of white (or black) rooks is N. Then N <= ab (the white constraint) and N <= (n-a)(n-b) (the black constraint). Therefore the largest value than N can take is upper-bounded by setting ab = (n-a)(n-b), so a = b = n/2 and N <= n^2/4. (End)

From Daniel Forgues, Feb 27 2015: (Start)

Observation: Suppose n >= 2 (omitting the 1 X 1 board):

for n = 2k, k >= 1, the values of a(n) are

{0, 2, 5, 9, 14, 21, ...}

for n = 2k+1, k >= 1, the values are

{1, 4, 7, 12, 17, 24, ...}

and then a(2k+1) - a(2k), k >= 1, yields

{1, 2, 2, 3, 3, 3, ...}.

(End)

From Peter Karpov, Apr 03 2016: (Start)

It appears that the maximal asymptotic density of one color for a configuration consisting of two pentagonal regions and their antipodal counterparts (with respect to the center) is 7/48.

Empirical observation: except for two small cases (n = 5, 9), the known values are given by a(n) = floor(7*n^2/48) (see A286283).

(End)

On a board with a maximal set of coexisting armies of queens, is every cell not occupied by a queen attacked by at least one queen of either color? - David A. Corneth, Oct 16 2018

This was problem C1 in Stephen Ainley's 1977 book cited below. His solution on page 31 exhibited precisely the construction rediscovered by Jubin in 2015. On pages 31 and 32 he listed his best results for n up to 30; these agree with a[n] for n up to 13, and with floor(7*n^2/48) for n from 14 to 30, EXCEPT that his best for n=27 was 105 (not 106). He also remarked that one could squeeze in another queen of one color when n is 4, 6, 8, 10, 11, 13, 14, 15, 19, 22, 26, 29. [When n=27, his best was 105 white queens and 107 black queens.] - Don Knuth, Apr 27 2019

The basic configuration of the "cracked block" solution for the n=20, 58-queen arrangement (see May 23 2017 example) is generalizable for all n = 16k+4, k >= 1. While the pattern is difficult to describe briefly enough for this site (each block can be broken down into component sections, each of these described in relation to n), all such n X n boards include the "corner" blocks extending n/4 squares east-to-west and n/2 squares north-to-south, while the "center" blocks extend n/4 squares east-to-west, starting n/4 + 1 squares from the nearest corner. The center white piece and "cracks" (as shown in the n=20 example) appear at the same relative positions in every board. - Bob Selcoe, May 16 2019

It is possible to construct a 15 X 15 board with 32 queens of one color and 34 of another (improving on Ainley's observation of 32 and 33 - see Knuth's Apr 27 2019 comment). Call the larger armies "aggressors". What might be the sequence of largest aggressors, for all optimal A250000(n)? Note that 34 may not be the largest possible aggressor for n=15. - Bob Selcoe, May 29 2019

Examples

			Some examples, in increasing order of size of board.
n=3: There is a unique solution (up to obvious symmetries):
+-------+
| W . . |
| . . . |
| . B . |
+-------+
n=4: There are ten inequivalent solutions, up to obvious symmetries (_Rob Pratt_, Jul 29 2015, with two more discovered by _Benoit Jubin_, Mar 17 2019; total of 10 confirmed by _Rob Pratt_, Mar 18 2019):
----------------------------------------------------------
|..B.||.B..||.B..||....||.BB.||..B.||...W||..B.|..B.|..W.|
|....||.B..||...B||.B.B||....||.B..||.B..||...B|B...|B...|
|...B||....||....||....||....||...W||..B.||.W..|...W|...B|
|WW..||W.W.||W.W.||W.W.||W..W||W...||W...||W...|.W..|.W..|
----------------------------------------------------------
n=5: One of the three solutions for n=5 puts one set of four queens in the corners and the other set in the squares a knight's move away, as follows:
+-----------+
| W . . . W |
| . . B . . |
| . B . B . |
| . . B . . |
| W . . . W |
+-----------+
There are two other solutions (up to symmetry) for n=5 (found by _Rob Pratt_, circa Sep 2014):
+-----------+
| . . B . B |
| W . . . . |
| . . B . B |
| W . . . . |
| . W . W . |
+-----------+
.
+-----------+
| . W . W . |
| . . W . . |
| B . . . B |
| . . W . . |
| B . . . B |
+-----------+
n=6: A solution for n=6:
+-------------+
| . W W . . . |
| . . W . . W |
| . . . . . W |
| . . . . . . |
| B . . . B . |
| B . . B B . |
+-------------+
n=8: a(8) = 9:
+-----------------+
| . . W W . . . . |
| . . W W . . . W |
| . . W . . . W W |
| . . . . . . W W |
| . B . . . . . . |
| B B . . . . . . |
| B B . . . B . . |
| B . . . B B . . | - _Rob Pratt_, Jul 29 2015
+-----------------+
n=9: A solution from _Bob Selcoe_, Feb 07 2015:
+-------------------+
| . B . B . B . B . |
| . . B . . . B . . |
| W . . . W . . . W |
| . . B . . . B . . |
| W . . . W . . . W |
| . . B . . . B . . |
| W . . . W . . . W |
| . . B . . . B . . |
| W . . . W . . . W |
+-------------------+
A solution for n=12 (from Prestwich/Beck paper):
+-------------------------+
| . . . B B B . . . . . B |
| . . . B B B . . . . B . |
| . . . B B B . . . B . B |
| . . . . B . . . . . B B |
| . . . . . . . . . B B B |
| . . . . . . . . . B B . |
| . . W . . . W . . . . . |
| . W W . . . . . . . . . |
| W W W . . . . . W . . . |
| W W . . . . . W W . . . |
| W . W . . . W W W . . . |
| . W . . . . W W W . . . |
+-------------------------+
A solution for n=13 (from Prestwich/Beck paper):
+---------------------------+
| B . . . B . B . . . B . B |
| . . W . . . . . W . . . . |
| . W . W . W . W . W . W . |
| . . W . . . . . W . . . . |
| B . . . B . B . . . B . B |
| . . W . . . . . W . . . . |
| B . . . B . B . . . B . B |
| . . W . . . . . W . . . . |
| . W . W . W . W . W . W . |
| . . W . . . . . W . . . . |
| B . . . B . B . . . B . B |
| . . W . . . . . W . . . . |
| B . . . B . B . . . B . B |
+---------------------------+
From _Bob Selcoe_, Feb 07 2015: (Start)
An alternative solution for n=13:
+---------------------------+
| . B . B . B . B . B . B . |
| . . B . . . B . . . B . . |
| W . . . W . . . W . . . W |
| . . B . . . B . . . B . . |
| W . . . W . . . W . . . W |
| . . B . . . B . . . B . . |
| W . . . W . . . W . . . W |
| . . B . . . B . . . B . . |
| W . . . W . . . W . . . W |
| . . B . . . B . . . B . . |
| W . . . W . . . W . . . W |
| . . B . . . B . . . B . . |
| W . . . W . . . W . . . W |
+---------------------------+
n=15, a fully symmetrical optimal configuration from _Paul Tabatabai_, Oct 16 2018:
+-------------------------------+
| B . B . B . . . . . B . B . B |
| . . . . . . W W W . . . . . . |
| B . B . B . . . . . B . B . B |
| . . . . . . W . W . . . . . . |
| B . B . . . . . . . . . B . B |
| . . . . . . W . W . . . . . . |
| . W . W . W . W . W . W . W . |
| . W . . . . W . W . . . . W . |
| . W . W . W . W . W . W . W . |
| . . . . . . W . W . . . . . . |
| B . B . . . . . . . . . B . B |
| . . . . . . W . W . . . . . . |
| B . B . B . . . . . B . B . B |
| . . . . . . W W W . . . . . . |
| B . B . B . . . . . B . B . B |
+-------------------------------+
n=17: A 42-queen arrangement (the best presently known) for n=17, from _Rob Pratt_, Feb 07 2014:
+-----------------------------------+
| . . . . W W W W W . . . . . . . . |
| . . . . W W W W W . . . . . . . . |
| . . . . W W W W W . . . . . . . W |
| . . . . W W W W . . . . . . . W W |
| . . . . W W W . . . . . . . W W W |
| . . . . . W . . . . . . . W W W W |
| . . . . . . . . . . . . . W W W W |
| . . . . . . . . . . . . . W W W . |
| . . . . . . . . . . . . . W W . . |
| . . B B . . . . . . . . . . . . . |
| . B B B . . . . . . . . . . . . . |
| B B B B . . . . . . . . . . . . . |
| B B B B . . . . . . . B . . . . . |
| B B B B . . . . . . B B B . . . . |
| B B B B . . . . . B B B B . . . . |
| B B B . . . . . . B B B B . . . . |
| B B . . . . . . . B B B B . . . . |
+-----------------------------------+
From _Bob Selcoe_, Feb 09 2015: (Start)
Two alternative 42-queen arrangements for n=17 (inspired by _Rob Pratt_). Other arrangements exist.
Alternative 1:
+-----------------------------------+
| . . . . . W W W W W . . . . . . . |
| . . . . . W W W W W . . . . . . . |
| . . . . . W W W W W . . . . . . W |
| . . . . . W W W W . . . . . . W W |
| . . . . . W W W . . . . . . W W W |
| . . . . . . W . . . . . . W W W W |
| . . . . . . . . . . . . . W W W W |
| . . . . . . . . . . . . . W W W . |
| . . . . . . . . . . . . . W W . . |
| . . . B B . . . . . . . . . . . . |
| . . B B B . . . . . . . . . . . . |
| . B B B B . . . . . . . . . . . . |
| B B B B B . . . . . . B B . . . . |
| B B B B B . . . . . B B B . . . . |
| B B B B . . . . . . B B B . . . . |
| B B B . . . . . . . B B B . . . . |
| B B . . . . . . . . B B B . . . . |
+-----------------------------------+
Alternative 2:
+-----------------------------------+
| . . . . W W W W . . . . . . . . W |
| . . . . W W W W . . . . . . . W W |
| . . . . W W W W . . . . . . W W W |
| . . . . W W W W . . . . . W W W W |
| . . . . . W W . . . . . . W W W W |
| . . . . . . . . . . . . . W W W W |
| . . . . . . . . . . . . . W W W . |
| . . . . . . . . . . . . . W W . . |
| . . . . . . . . . . . . . W . . . |
| . . B B . . . . . . . . . . . . . |
| . B B B . . . . . . . . . . . . . |
| B B B B . . . . . . . B . . . . . |
| B B B B . . . . . . B B B . . . . |
| B B B . . . . . . B B B B . . . . |
| B B . . . . . . B B B B B . . . . |
| B . . . . . . . B B B B B . . . . |
| . . . . . . . . B B B B B . . . . |
+-----------------------------------+
Example of an alternative n=20, 58-queen arrangement with "cracked" blocks from _Bob Selcoe_, May 23 2017:
+-----------------------------------------+
| . . . . . W W W W W . . . . . . . . W . |
| . . . . . W W W W W . . . . . . . W . W |
| . . . . . W W W W W . . . . . . W . W W |
| . . . . . W W W W W . . . . . W . W W W |
| . . . . . W W W W . . . . . . . W W W W |
| . . . . . W W W . . . . . . . W W W W W |
| . . . . . . W . . . . . . . . W W W W . |
| . . . . . . . . . . . . . . . W W W . . |
| . . . . . . . . . . . . . . . W W . . . |
| . . . . . . . . . W . . . . . W . . . . |
| . . . B B . . . . . . . . . . . . . . . |
| . . B B B . . . . . . . . . . . . . . . |
| . B B B B . . . . . . . . . . . . . . . |
| B B B B B . . . . . . . B . . . . . . . |
| B B B B . . . . . . . B B B . . . . . . |
| B B B . B . . . . . B B B B B . . . . . |
| B B . B . . . . . . B B B B B . . . . . |
| B . B . . . . . . . B B B B B . . . . . |
| . B . . . . . . . . B B B B B . . . . . |
| B . . . . . . . . . B B B B B . . . . . |
+-----------------------------------------+
Pattern for n = 4m; four chessboards total.
Board 1: n=12, a(12)=21:
+-------------------------+
| . . . W W W . . . . . . |
| . . . W W W . . . . . W |
| . . . W W W . . . . W W |
| . . . . W . . . . W W W |
| . . . . . . . . . W W W |
| . . . . . . . . . W W . |
| . . B . . . . . . . . . |
| . B B . . . . . . . . . |
| B B B . . . . . B . . . |
| B B B . . . . B B . . . |
| B B . . . . B B B . . . |
| B . . . . . B B B . . . |
+-------------------------+
Board 2: n=16, 37-queen arrangement:
+---------------------------------+
| . . . . W W W W . . . . . . . . |
| . . . . W W W W . . . . . . . W |
| . . . . W W W W . . . . . . W W |
| . . . . W W W W . . . . . W W W |
| . . . . . W W . . . . . W W W W |
| . . . . . . . . . . . . W W W W |
| . . . . . . . . . . . . W W W . |
| . . . . . . . . . . . . W W . . |
| . . . B . . . . . . . . . . . . |
| . . B B . . . . . . . . . . . . |
| . B B B . . . . . . . . . . . . |
| B B B B . . . . . . B B . . . . |
| B B B B . . . . . B B B . . . . |
| B B B . . . . . B B B B . . . . |
| B B . . . . . . B B B B . . . . |
| B . . . . . . . B B B B . . . . |
+---------------------------------+
Board 3: n=20, 58-queen arrangement:
+-----------------------------------------+
| . . . . . W W W W W . . . . . . . . . . |
| . . . . . W W W W W . . . . . . . . . W |
| . . . . . W W W W W . . . . . . . . W W |
| . . . . . W W W W W . . . . . . . W W W |
| . . . . . W W W W W . . . . . . W W W W |
| . . . . . . W W W . . . . . . W W W W W |
| . . . . . . . W . . . . . . . W W W W W |
| . . . . . . . . . . . . . . . W W W W . |
| . . . . . . . . . . . . . . . W W W . . |
| . . . . . . . . . . . . . . . W W . . . |
| . . . . B . . . . . . . . . . . . . . . |
| . . . B B . . . . . . . . . . . . . . . |
| . . B B B . . . . . . . . . . . . . . . |
| . B B B B . . . . . . . . B . . . . . . |
| B B B B B . . . . . . . B B B . . . . . |
| B B B B B . . . . . . B B B B . . . . . |
| B B B B . . . . . . B B B B B . . . . . |
| B B B . . . . . . . B B B B B . . . . . |
| B B . . . . . . . . B B B B B . . . . . |
| B . . . . . . . . . B B B B B . . . . . |
+-----------------------------------------+
Board 4: n=24, 83-queen arrangement:
+-------------------------------------------------+
| . . . . . . W W W W W W . . . . . . . . . . . . |
| . . . . . . W W W W W W . . . . . . . . . . . W |
| . . . . . . W W W W W W . . . . . . . . . . W W |
| . . . . . . W W W W W W . . . . . . . . . W W W |
| . . . . . . W W W W W W . . . . . . . . W W W W |
| . . . . . . W W W W W W . . . . . . . W W W W W |
| . . . . . . . W W W W . . . . . . . W W W W W W |
| . . . . . . . . W W . . . . . . . . W W W W W W |
| . . . . . . . . . . . . . . . . . . W W W W W . |
| . . . . . . . . . . . . . . . . . . W W W W . . |
| . . . . . . . . . . . . . . . . . . W W W . . . |
| . . . . . . . . . . . . . . . . . . W W . . . . |
| . . . . . B . . . . . . . . . . . . . . . . . . |
| . . . . B B . . . . . . . . . . . . . . . . . . |
| . . . B B B . . . . . . . . . . . . . . . . . . |
| . . B B B B . . . . . . . . . . . . . . . . . . |
| . B B B B B . . . . . . . . . B B . . . . . . . |
| B B B B B B . . . . . . . . B B B B . . . . . . |
| B B B B B B . . . . . . . B B B B B . . . . . . |
| B B B B B . . . . . . . B B B B B B . . . . . . |
| B B B B . . . . . . . . B B B B B B . . . . . . |
| B B B . . . . . . . . . B B B B B B . . . . . . |
| B B . . . . . . . . . . B B B B B B . . . . . . |
| B . . . . . . . . . . . B B B B B B . . . . . . |
+-------------------------------------------------+
(End)
Example of an alternative n=20, 58-queen arrangement with "cracked" blocks from _Bob Selcoe_, May 23 2017:
+-----------------------------------------+
| . . . . . W W W W W . . . . . . . . W . |
| . . . . . W W W W W . . . . . . . W . W |
| . . . . . W W W W W . . . . . . W . W W |
| . . . . . W W W W W . . . . . W . W W W |
| . . . . . W W W W . . . . . . . W W W W |
| . . . . . W W W . . . . . . . W W W W W |
| . . . . . . W . . . . . . . . W W W W . |
| . . . . . . . . . . . . . . . W W W . . |
| . . . . . . . . . . . . . . . W W . . . |
| . . . . . . . . . W . . . . . W . . . . |
| . . . B B . . . . . . . . . . . . . . . |
| . . B B B . . . . . . . . . . . . . . . |
| . B B B B . . . . . . . . . . . . . . . |
| B B B B B . . . . . . . B . . . . . . . |
| B B B B . . . . . . . B B B . . . . . . |
| B B B . B . . . . . B B B B B . . . . . |
| B B . B . . . . . . B B B B B . . . . . |
| B . B . . . . . . . B B B B B . . . . . |
| . B . . . . . . . . B B B B B . . . . . |
| B . . . . . . . . . B B B B B . . . . . |
+-----------------------------------------+
.
n = 24: An 84-queen arrangement found by _Benoit Jubin_, Feb 24 2015 (see Comments above).
+-------------------------------------------------+
| . . . . . . W W W W W W . . . . . . . . . . . . |
| . . . . . . W W W W W W . . . . . . . . . . . W |
| . . . . . . W W W W W W . . . . . . . . . . W W |
| . . . . . . W W W W W W . . . . . . . . . W W W |
| . . . . . . W W W W W W . . . . . . . . W W W W |
| . . . . . . W W W W W . . . . . . . . W W W W W |
| . . . . . . . W W W . . . . . . . . W W W W W W |
| . . . . . . . . W . . . . . . . . . W W W W W W |
| . . . . . . . . . . . . . . . . . . W W W W W W |
| . . . . . . . . . . . . . . . . . . W W W W W . |
| . . . . . . . . . . . . . . . . . . W W W W . . |
| . . . . . . . . . . . . . . . . . . W W W . . . |
| . . . . B B . . . . . . . . . . . . . . . . . . |
| . . . B B B . . . . . . . . . . . . . . . . . . |
| . . B B B B . . . . . . . . . . . . . . . . . . |
| . B B B B B . . . . . . . . . . . . . . . . . . |
| B B B B B B . . . . . . . . . . B . . . . . . . |
| B B B B B B . . . . . . . . . B B B . . . . . . |
| B B B B B B . . . . . . . . B B B B . . . . . . |
| B B B B B . . . . . . . . B B B B B . . . . . . |
| B B B B . . . . . . . . B B B B B B . . . . . . |
| B B B . . . . . . . . . B B B B B B . . . . . . |
| B B . . . . . . . . . . B B B B B B . . . . . . |
| B . . . . . . . . . . . B B B B B B . . . . . . |
+-------------------------------------------------+
.
A solution for n = 27 with 106 queens found by _Dmitry Kamenetsky_, Oct 18 2019
+-------------------------------------------------------+
| . . . . . . . . . . . . W W W W W W W . . . . . . . . |
| . . . . . . . . . . . . W W W W W W W . . . . . . . . |
| W . . . . . . . . . . . W W W W W W W . . . . . . . . |
| W W . . . . . . . . . . W W W W W W W . . . . . . . . |
| W W W . . . . . . . . . W W W W W W W . . . . . . . . |
| W W W W . . . . . . . . . W W W W W W . . . . . . . . |
| W W W W W . . . . . . . . . W W W W W . . . . . . . . |
| W W W W W W . . . . . . . . . W W W . . . . . . . . . |
| W W W W W W . . . . . . . . . . W . W . . . . . . . . |
| W W W W W W . . . . . . . . . . . W . . . . . . . . . |
| W W W W W W . . . . . . . . . . . . . . . . . . . . . |
| . W W W W W . . . . . . . . . . . . . . . . . . . . . |
| . . W W W W . . . . . . . . . . . . . . . . . . . . . |
| . . . W W W . . . . . . . . . . . . . . . . . . . . . |
| . . . . W W . . . . . . W . . . . . . . . . . . . . . |
| . . . . . . . . . . . . . . . . . . . B B B B . . . . |
| . . . . . . . . . . . . . . . . . . . B B B B B . . . |
| . . . . . . . . . . . . . . . . . . . B B B B B B . . |
| . . . . . . . B . . . . . . . . . . . B B B B B B B . |
| . . . . . . B . B . . . . . . . . . . B B B B B B B B |
| . . . . . . . B B B . . . . . . . . . B B B B B B B B |
| . . . . . . B B B B B . . . . . . . . . B B B B B B B |
| . . . . . . B B B B B B . . . . . . . . . B B B B B B |
| . . . . . . B B B B B B . . . . . . . . . . B B B B B |
| . . . . . . B B B B B B . . . . . . . . . . . B B B B |
| . . . . . . B B B B B B . . . . . . . . . . . . B B B |
| . . . . . . B B B B B B . . . . . . . . . . . . . B B |
+-------------------------------------------------------+
		

References

• Stephen Ainley, Mathematical Puzzles. London: G Bell & Sons, 1977.
• Donald E. Knuth, Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, page 180, Problem 488; see also pp. 282-283.

Links

• Stephen Ainley, Mathematical Puzzles, London: G Bell & Sons, 1977. [Annotated scan of page 27]
• Stephen Ainley, Mathematical Puzzles, London: G Bell & Sons, 1977. [Annotated scan of a portion of page 31]
• Stephen Ainley, Mathematical Puzzles, London: G Bell & Sons, 1977. [Annotated scan of a portion of page 32]
• Robert A. Bosch, Peaceably coexisting armies of queens, Optima (Newsletter of the Mathematical Programming Society) 62.6-9 (1999): 271.
• Robert A. Bosch, Peaceably coexisting armies of queens, Optima (Newsletter of the Mathematical Programming Society) 62.6-9 (1999): 271. [Scanned copy of page containing the problem, with permission]
• Robert A. Bosch, Armies of Queens, Revisited, Optima (Newsletter of the Mathematical Programming Society) 64 (2000): 15.
• Robert A. Bosch, Armies of Queens, Revisited, Optima (Newsletter of the Mathematical Programming Society) 64 (2000): 15. [Scanned copy of section of page containing the article, with permission]
• Katie Clinch, Matthew Drescher, Tony Huynh, and Abdallah Saffidine, Constructions, bounds, and algorithms for peaceable queens, arXiv:2406.06974 [math.CO], 2024. See p. 1.
• Brady Haran and N. J. A. Sloane, Peaceable Queens, Numberphile video (2019).
• Daniel M. Kane, Asymptotic Results for the Queen Packing Problem, arXiv:1703.04538 [math.CO], 2017.
• Michael De Vlieger, "Peace to the Max" T-shirt illustrating a(11)=17
• Michael De Vlieger, "Peace to the Max" T-shirt illustrating a(11)=17 [Version with no background, suitable for printing]
• Michael De Vlieger, Graphic illustrations of other solutions
• Benoit Jubin, Improved lower bound for A250000, Posting to Sequence Fans Mailing List, Feb 24 2015, with comments from Rob Pratt and Bob Selcoe.
• Dmitry Kamenetsky, Best known solutions for 12 <= n <= 30.
• Dmitry Kamenetsky, Java program to compute the best known solutions.
• Peter Karpov, InvMem, see Item 22
• Peter Karpov, InvMem, see Item 22 [Scanned copy of Item 22, with permission.]
• Peter Karpov, An asymptotic configuration with density 7/48 (Not known to be optimal.)
• Donald Knuth, Problem presented at Ron Graham's 80th Birthday Dinner (June 2015; includes an extension to three armies).
• Steven Prestwich and J. Christopher Beck, Exploiting Dominance in Three Symmetric Problems, in Proceedings Fourth International Workshop on Symmetry and Constraint Satisfaction Problems (SymCon'04), (2004) pp. 63-70; also available from http://zeynep.web.cs.unibo.it/SymCon04/proceedings.html
• N. J. A. Sloane, Confessions of a Sequence Addict (AofA2017), slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
• Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, Models and symmetry breaking for 'Peaceable armies of queens', Lecture Notes in Computer Science 3011 (2004), 271-286. [Version on St Andrews web site, 16 pages.]
• Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, Models and symmetry breaking for 'Peaceable armies of queens', Lecture Notes in Computer Science 3011 (2004), 271-286. [Version on ResearchGate web site, 17 pages]
• Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, Models and symmetry breaking for 'Peaceable armies of queens', Lecture Notes in Computer Science 3011 (2004), 271-286. [Cached copy, from ResearchGate]
• Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, Equal sized armies of queens on an 11x11 board (Fig. 2 from the reference).
• Paul Tabatabai, Three illustrations for a(14) = 28.
• Yukun Yao and Doron Zeilberger, Numerical and Symbolic Studies of the Peaceable Queens Problem, Feb 14, 2019; see also arXiv:1902.05886 [math.CO], 2019, Exp. Math. 31 (2022) 269-279

Crossrefs

A260680 gives number of solutions.

Cf. A002620, A274947, A274948, A286283 (lower bound).

See A000170, A002562, A319284, etc., for the classic non-attacking queens problem.

See also A279405 (torus version), A176222 (peaceable kings), A002620 (peaceable rooks), A355509 (peaceable knights).

Formula

There is an asymptotic lower bound of (9/64)*n^2. But see Comments for a better lower bound.

Extensions

Uniqueness of n = 5 example corrected by Rob Pratt, Nov 30 2014

a(12)-a(13) obtained from Prestwich/Beck paper by Rob Pratt, Nov 30 2014

More examples from Rob Pratt, Dec 01 2014

a(1)-a(13) confirmed and bounds added for n = 14 to 20 obtained via integer linear programming by Rob Pratt, Dec 01 2014

28 <= a(14) <= 43, 32 <= a(15) <= 53, 37 <= a(16) <= 64, 42 <= a(17) <= 72, 47 <= a(18) <= 81, 52 <= a(19) <= 90, 58 <= a(20) <= 100. - Rob Pratt, Dec 01 2014

Bounds obtained by simulated annealing: a(21) >= 64, a(22) >= 70, a(23) >= 77, a(24) >= 84. - Peter Karpov, Apr 03 2016

a(14)-a(15) from Paul Tabatabai using integer programming, Oct 16 2018

Edited by N. J. A. Sloane, Nov 18 2018 to include comments from Benoit Jubin, Feb 24 2015 which were posted to the Sequence Fans Mailing List but were not added to this entry until today.

Counts for n=4 edited by N. J. A. Sloane, Mar 19 2019. See A260680 for more information.