login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
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 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)

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 a few small cases (n = 5, 9), the known values are given by a(n) = floor(7*n^2/48).

(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.6-9 (1999): 271.

Bosch, Robert A., Armies of Queens, Revisited, Optima (Newsletter of the Mathematical Programming Society) 64 (2000): 15.

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" 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

Steven Prestwich and J. Christopher Beck, Exploiting Dominance in Three Symmetric Problems, in: Fourth International Workshop on Symmetry and Constraint Satisfaction Problems (2004).

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.

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.

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)

Peter Karpov, InvMem, Item 22

Peter Karpov, Asymptotic configuration with density 7/48

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 42-queen 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 42-queen 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, 37-queen 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, 58-queen 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, 83-queen 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, 84-queen arrangement (variation on n=4m pattern above. For m>=6, the new pattern is generalizable as an improvement over the previously-shown pattern and can be used for a(n) = Floor(7/48 n^2) arrangements, following Peter Karpov's April 3, 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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 29 18:39 EDT 2017. Contains 284273 sequences.