

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.


7



0, 0, 1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Two solutions are regarded as equivalent if one can be obtained from the other by rotations, reflections, interchanging the colors (a group of order 16). For n=1,2,3,4,5 the number of solutions is respectively 1,1,1,8,3. What is the number of solutions for n=6?  Rob Pratt and N. J. A. Sloane, Jul 29 2015 Answer: 34, see A260680.  Luca Petrone, Mar 11 2016
From Bob Selcoe, Feb 09 2015: (Start)
For n = 4m, a generalized quasisymmetric pattern of queen arrangements exists showing that a(n) >= ceiling((n+4)(n2)/8) + floor((n4)^2/64) == (m+1)(2m1) + A002620(m1).
For n= 4m1, a slightly different pattern exists showing that a(n) >= m(2m1) + 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)
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)


LINKS

Table of n, a(n) for n=1..13.
Bosch, Robert A., Peaceably coexisting armies of queens, Optima (Newsletter of the Mathematical Programming Society) 62.69 (1999): 271.
Bosch, Robert A., Peaceably coexisting armies of queens, Optima (Newsletter of the Mathematical Programming Society) 62.69 (1999): 271. [Scanned copy of page containing the problem, with permission]
Bosch, Robert A., Armies of Queens, Revisited, Optima (Newsletter of the Mathematical Programming Society) 64 (2000): 15.
Bosch, Robert A., 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]
Daniel M. Kane, Asymptotic Results for the Queen Packing Problem, arXiv:1703.04538 [math.CO], Mar 16 2017
Michael De Vlieger, "Peace to the Max" Tshirt illustrating a(11)=17
Michael De Vlieger, "Peace to the Max" Tshirt illustrating a(11)=17 [Version with no background, suitable for printing]
Michael De Vlieger, Graphic illustrations of other solutions
Peter Karpov, InvMem, see Item 22
Peter Karpov, InvMem, see Item 22 [Scanned copy of Item 22, with permission.]
Peter Karpov, Asymptotic configuration with density 7/48
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. 6370; also available from http://zeynep.web.cs.unibo.it/SymCon04/proceedings.html
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), 271286. [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), 271286. [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), 271286. [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)


FORMULA

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


EXAMPLE

Some examples, in increasing order of size of board.
n=3: There is a unique solution (up to obvious symmetries):

W..
...
.B.

n=4: From Rob Pratt, Jul 29 2015. There are eight inequivalent solutions (up to obvious symmetries):

 ..B.  .B..  .B..  .... 
 ....  .B..  ...B  .B.B 
 ...B  ....  ....  .... 
 WW..  W.W.  W.W.  W.W. 

 .BB.  ..B.  ...W  ..B. 
 ....  .B..  .B..  ...B 
 ....  ...W  ..B.  .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:

.WW...
..W..W
.....W
......
B...B.
B..BB.

n=8: a(8) = 9:
..WW....
..WW...W
..W...WW
......WW
.B......
BB......
BB...B..
B...BB..  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):

...BBB.....B
...BBB....B.
...BBB...B.B
....B.....BB
.........BBB
.........BB.
..W...W.....
.WW.........
WWW.....W...
WW.....WW...
W.W...WWW...
.W....WWW...

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=17: A 42queen arrangement (the best presently known) for n=17, from Rob Pratt, Feb 07 2014:

....WWWWW........
....WWWWW........
....WWWWW.......W
....WWWW.......WW
....WWW.......WWW
.....W.......WWWW
.............WWWW
.............WWW.
.............WW..
..BB.............
.BBB.............
BBBB.............
BBBB.......B.....
BBBB......BBB....
BBBB.....BBBB....
BBB......BBBB....
BB.......BBBB....

From Bob Selcoe, Feb 09 2015 (Start):
Two alternative 42queen arrangements for n=17 (inspired by Rob Pratt). Other arrangements exist.
Alternative 1:

.....WWWWW.......
.....WWWWW.......
.....WWWWW......W
.....WWWW......WW
.....WWW......WWW
......W......WWWW
.............WWWW
.............WWW.
.............WW..
...BB............
..BBB............
.BBBB............
BBBBB......BB....
BBBBB.....BBB....
BBBB......BBB....
BBB.......BBB....
BB........BBB....

Alternative 2:

....WWWW........W
....WWWW.......WW
....WWWW......WWW
....WWWW.....WWWW
.....WW......WWWW
.............WWWW
.............WWW.
.............WW..
.............W...
..BB.............
.BBB.............
BBBB.......B.....
BBBB......BBB....
BBB......BBBB....
BB......BBBBB....
B.......BBBBB....
........BBBBB....

Pattern for n = 4m; four chessboards total.
Board 1: n=12, a(12)=21:

...WWW......
...WWW.....W
...WWW....WW
....W....WWW
.........WWW
.........WW.
..B.........
.BB.........
BBB.....B...
BBB....BB...
BB....BBB...
B.....BBB...

Board 2: n=16, 37queen arrangement:

....WWWW........
....WWWW.......W
....WWWW......WW
....WWWW.....WWW
.....WW.....WWWW
............WWWW
............WWW.
............WW..
...B............
..BB............
.BBB............
BBBB......BB....
BBBB.....BBB....
BBB.....BBBB....
BB......BBBB....
B.......BBBB....

Board 3: n=20, 58queen arrangement:

.....WWWWW..........
.....WWWWW.........W
.....WWWWW........WW
.....WWWWW.......WWW
.....WWWWW......WWWW
......WWW......WWWWW
.......W.......WWWWW
...............WWWW.
...............WWW..
...............WW...
....B...............
...BB...............
..BBB...............
.BBBB........B......
BBBBB.......BBB.....
BBBBB......BBBB.....
BBBB......BBBBB.....
BBB.......BBBBB.....
BB........BBBBB.....
B.........BBBBB.....

Board 4: n=24, 83queen arrangement:

......WWWWWW............
......WWWWWW...........W
......WWWWWW..........WW
......WWWWWW.........WWW
......WWWWWW........WWWW
......WWWWWW.......WWWWW
.......WWWW.......WWWWWW
........WW........WWWWWW
..................WWWWW.
..................WWWW..
..................WWW...
..................WW....
.....B..................
....BB..................
...BBB..................
..BBBB..................
.BBBBB.........BB.......
BBBBBB........BBBB......
BBBBBB.......BBBBB......
BBBBB.......BBBBBB......
BBBB........BBBBBB......
BBB.........BBBBBB......
BB..........BBBBBB......
B...........BBBBBB......

(End)

n=24, 84queen arrangement (variation on n=4m pattern above. For m>=6, the new pattern is generalizable as an improvement over the previouslyshown pattern and can be used to achieve arrangements showing that a(n) >= Floor(7*n^2/48), as in Peter Karpov's Apr 03 2016 observation).  Bob Selcoe, Apr 14 2016

......WWWWWW............
......WWWWWW...........W
......WWWWWW..........WW
......WWWWWW.........WWW
......WWWWWW........WWWW
......WWWWW........WWWWW
.......WWW........WWWWWW
........W.........WWWWWW
..................WWWWWW
..................WWWWW.
..................WWWW..
..................WWW...
....BB..................
...BBB..................
..BBBB..................
.BBBBB..................
BBBBBB..........B.......
BBBBBB.........BBB......
BBBBBB........BBBB......
BBBBB........BBBBB......
BBBB........BBBBBB......
BBB.........BBBBBB......
BB..........BBBBBB......
B...........BBBBBB......



CROSSREFS

A260680 gives number of solutions.
Cf. A002620, A274947, A274948, A286283.
See A000170, A002562, etc., for the classical nonattacking queens problem.
Sequence in context: A027861 A219648 A062428 * A056833 A275534 A212661
Adjacent sequences: A249997 A249998 A249999 * A250001 A250002 A250003


KEYWORD

nonn,nice,more,changed


AUTHOR

Don Knuth, Aug 01 2014


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


STATUS

approved



