cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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.

This page as a plain text file.
%I A250000 #354 Jan 07 2025 08:08:09
%S A250000 0,0,1,2,4,5,7,9,12,14,17,21,24,28,32
%N 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.
%C A250000 Comments from _N. J. A. Sloane_, May 22 2019: (Start)
%C A250000 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.
%C A250000 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.
%C A250000 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)
%C A250000 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).
%C A250000 For the number of inequivalent solutions see A260680.
%C A250000 From _Bob Selcoe_, Feb 09 2015: (Start)
%C A250000 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).
%C A250000 For n = 4m-1, a slightly different pattern exists showing that a(n) >= m(2m-1) + A002620(m).
%C A250000 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.
%C A250000 For all n >= 16, a(n) > ceiling(9n^2/64), which is the best asymptotic lower bound presently known.
%C A250000 It is likely that similar "block" patterns exist for n = {4m+1, 4m+2}.
%C A250000 (End)
%C A250000 Comments from _Benoit Jubin_, Feb 24 2015: (Start)
%C A250000 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.
%C A250000 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.
%C A250000 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.
%C A250000 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).
%C A250000 Using an easy upper bound, one has asymptotically
%C A250000 (2+1/3)*(n/4)^2 < a(n) < 4*(n/4)^2.
%C A250000 Nov 20 2018: _Benoit Jubin_ explained how his upper bound was obtained, as follows:
%C A250000 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)
%C A250000 From _Daniel Forgues_, Feb 27 2015: (Start)
%C A250000 Observation: Suppose n >= 2 (omitting the 1 X 1 board):
%C A250000 for n = 2k, k >= 1, the values of a(n) are
%C A250000   {0, 2, 5, 9, 14, 21, ...}
%C A250000 for n = 2k+1, k >= 1, the values are
%C A250000   {1, 4, 7, 12, 17, 24, ...}
%C A250000 and then a(2k+1) - a(2k), k >= 1, yields
%C A250000   {1, 2, 2, 3, 3, 3, ...}.
%C A250000 (End)
%C A250000 From _Peter Karpov_, Apr 03 2016: (Start)
%C A250000 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.
%C A250000 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).
%C A250000 (End)
%C A250000 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
%C A250000 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
%C A250000 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
%C A250000 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
%D A250000 Stephen Ainley, Mathematical Puzzles. London: G Bell & Sons, 1977.
%D A250000 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.
%H A250000 Stephen Ainley, <a href="/A250000/a250000_4.png">Mathematical Puzzles</a>, London: G Bell & Sons, 1977. [Annotated scan of page 27]
%H A250000 Stephen Ainley, <a href="/A250000/a250000_5.png">Mathematical Puzzles</a>, London: G Bell & Sons, 1977. [Annotated scan of a portion of page 31]
%H A250000 Stephen Ainley, <a href="/A250000/a250000_6.png">Mathematical Puzzles</a>, London: G Bell & Sons, 1977. [Annotated scan of a portion of page 32]
%H A250000 Robert A. Bosch, <a href="http://www.mathopt.org/Optima-Issues/optima62.pdf">Peaceably coexisting armies of queens</a>, Optima (Newsletter of the Mathematical Programming Society) 62.6-9 (1999): 271.
%H A250000 Robert A. Bosch, <a href="/A250000/a250000_1.png">Peaceably coexisting armies of queens</a>, Optima (Newsletter of the Mathematical Programming Society) 62.6-9 (1999): 271. [Scanned copy of page containing the problem, with permission]
%H A250000 Robert A. Bosch, <a href="http://www.mathopt.org/Optima-Issues/optima64.pdf">Armies of Queens, Revisited</a>, Optima (Newsletter of the Mathematical Programming Society) 64 (2000): 15.
%H A250000 Robert A. Bosch, <a href="/A250000/a250000_2.png">Armies of Queens, Revisited</a>, Optima (Newsletter of the Mathematical Programming Society) 64 (2000): 15. [Scanned copy of section of page containing the article, with permission]
%H A250000 Katie Clinch, Matthew Drescher, Tony Huynh, and Abdallah Saffidine, <a href="https://arxiv.org/abs/2406.06974">Constructions, bounds, and algorithms for peaceable queens</a>, arXiv:2406.06974 [math.CO], 2024. See p. 1.
%H A250000 Brady Haran and N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=IN1fPtY9jYg">Peaceable Queens</a>, Numberphile video (2019).
%H A250000 Daniel M. Kane, <a href="https://arxiv.org/abs/1703.04538">Asymptotic Results for the Queen Packing Problem</a>, arXiv:1703.04538 [math.CO], 2017.
%H A250000 Michael De Vlieger, <a href="/A250000/a250000_MDV-1.png">"Peace to the Max" T-shirt illustrating a(11)=17</a>
%H A250000 Michael De Vlieger, <a href="/A250000/a250000-MDV-2.jpg">"Peace to the Max" T-shirt illustrating a(11)=17</a> [Version with no background, suitable for printing]
%H A250000 Michael De Vlieger, <a href="/A250000/a250000-MDV-2-Boards.pdf">Graphic illustrations of other solutions</a>
%H A250000 Benoit Jubin, <a href="/A250000/a250000_1.txt">Improved lower bound for A250000</a>, Posting to Sequence Fans Mailing List, Feb 24 2015, with comments from Rob Pratt and Bob Selcoe.
%H A250000 Dmitry Kamenetsky, <a href="/A250000/a250000_3.txt">Best known solutions for 12 <= n <= 30.</a>
%H A250000 Dmitry Kamenetsky, <a href="/A250000/a250000_1.java.txt">Java program to compute the best known solutions.</a>
%H A250000 Peter Karpov, <a href="http://inversed.ru/InvMem.htm#InvMem_22">InvMem, see Item 22</a>
%H A250000 Peter Karpov, <a href="/A250000/a250000_3.png">InvMem, see Item 22</a> [Scanned copy of Item 22, with permission.]
%H A250000 Peter Karpov, <a href="/A250000/a250000.png">An asymptotic configuration with density 7/48</a> (Not known to be optimal.)
%H A250000 Donald Knuth, <a href="//cs.stanford.edu/~knuth/problem-peaceful.pdf">Problem presented at Ron Graham's 80th Birthday Dinner</a> (June 2015; includes an extension to three armies).
%H A250000 Steven Prestwich and J. Christopher Beck, <a href="http://tidel.mie.utoronto.ca/pubs/pseudo.pdf">Exploiting Dominance in Three Symmetric Problems</a>, 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
%H A250000 N. J. A. Sloane, <a href="/A195264/a195264.pdf">Confessions of a Sequence Addict (AofA2017)</a>, slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
%H A250000 Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, <a href="http://ipg.host.cs.st-andrews.ac.uk/papers/spgW9.pdf">Models and symmetry breaking for 'Peaceable armies of queens'</a>, Lecture Notes in Computer Science 3011 (2004), 271-286. [Version on St Andrews web site, 16 pages.]
%H A250000 Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, <a href="https://www.researchgate.net/profile/Karen_Petrie/publication/221353569_Models_and_Symmetry_Breaking_for_%27Peaceable_Armies_of_Queens%27/links/0fcfd5111456cdbaa6000000.pdf">Models and symmetry breaking for 'Peaceable armies of queens'</a>, Lecture Notes in Computer Science 3011 (2004), 271-286. [Version on ResearchGate web site, 17 pages]
%H A250000 Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, <a href="/A250000/a250000.pdf">Models and symmetry breaking for 'Peaceable armies of queens'</a>, Lecture Notes in Computer Science 3011 (2004), 271-286. [Cached copy, from ResearchGate]
%H A250000 Barbara M. Smith, Karen E. Petrie, and Ian P. Gent, <a href="/A245783/a245783.pdf">Equal sized armies of queens on an 11x11 board</a> (Fig. 2 from the reference).
%H A250000 Paul Tabatabai, <a href="/A250000/a250000.txt">Three illustrations for a(14) = 28</a>.
%H A250000 Yukun Yao and Doron Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/peaceable.pdf">Numerical and Symbolic Studies of the Peaceable Queens Problem</a>, Feb 14, 2019; see also <a href="https://arxiv.org/abs/1902.05886">arXiv:1902.05886</a> [math.CO], 2019, <a href="https://doi.org/10.1080/10586458.2019.1616338">Exp. Math. 31 (2022) 269-279</a>
%F A250000 There is an asymptotic lower bound of (9/64)*n^2. But see Comments for a better lower bound.
%e A250000 Some examples, in increasing order of size of board.
%e A250000 n=3: There is a unique solution (up to obvious symmetries):
%e A250000 +-------+
%e A250000 | W . . |
%e A250000 | . . . |
%e A250000 | . B . |
%e A250000 +-------+
%e A250000 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):
%e A250000 ----------------------------------------------------------
%e A250000 |..B.||.B..||.B..||....||.BB.||..B.||...W||..B.|..B.|..W.|
%e A250000 |....||.B..||...B||.B.B||....||.B..||.B..||...B|B...|B...|
%e A250000 |...B||....||....||....||....||...W||..B.||.W..|...W|...B|
%e A250000 |WW..||W.W.||W.W.||W.W.||W..W||W...||W...||W...|.W..|.W..|
%e A250000 ----------------------------------------------------------
%e A250000 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:
%e A250000 +-----------+
%e A250000 | W . . . W |
%e A250000 | . . B . . |
%e A250000 | . B . B . |
%e A250000 | . . B . . |
%e A250000 | W . . . W |
%e A250000 +-----------+
%e A250000 There are two other solutions (up to symmetry) for n=5 (found by _Rob Pratt_, circa Sep 2014):
%e A250000 +-----------+
%e A250000 | . . B . B |
%e A250000 | W . . . . |
%e A250000 | . . B . B |
%e A250000 | W . . . . |
%e A250000 | . W . W . |
%e A250000 +-----------+
%e A250000 .
%e A250000 +-----------+
%e A250000 | . W . W . |
%e A250000 | . . W . . |
%e A250000 | B . . . B |
%e A250000 | . . W . . |
%e A250000 | B . . . B |
%e A250000 +-----------+
%e A250000 n=6: A solution for n=6:
%e A250000 +-------------+
%e A250000 | . W W . . . |
%e A250000 | . . W . . W |
%e A250000 | . . . . . W |
%e A250000 | . . . . . . |
%e A250000 | B . . . B . |
%e A250000 | B . . B B . |
%e A250000 +-------------+
%e A250000 n=8: a(8) = 9:
%e A250000 +-----------------+
%e A250000 | . . W W . . . . |
%e A250000 | . . W W . . . W |
%e A250000 | . . W . . . W W |
%e A250000 | . . . . . . W W |
%e A250000 | . B . . . . . . |
%e A250000 | B B . . . . . . |
%e A250000 | B B . . . B . . |
%e A250000 | B . . . B B . . | - _Rob Pratt_, Jul 29 2015
%e A250000 +-----------------+
%e A250000 n=9: A solution from _Bob Selcoe_, Feb 07 2015:
%e A250000 +-------------------+
%e A250000 | . B . B . B . B . |
%e A250000 | . . B . . . B . . |
%e A250000 | W . . . W . . . W |
%e A250000 | . . B . . . B . . |
%e A250000 | W . . . W . . . W |
%e A250000 | . . B . . . B . . |
%e A250000 | W . . . W . . . W |
%e A250000 | . . B . . . B . . |
%e A250000 | W . . . W . . . W |
%e A250000 +-------------------+
%e A250000 A solution for n=12 (from Prestwich/Beck paper):
%e A250000 +-------------------------+
%e A250000 | . . . B B B . . . . . B |
%e A250000 | . . . B B B . . . . B . |
%e A250000 | . . . B B B . . . B . B |
%e A250000 | . . . . B . . . . . B B |
%e A250000 | . . . . . . . . . B B B |
%e A250000 | . . . . . . . . . B B . |
%e A250000 | . . W . . . W . . . . . |
%e A250000 | . W W . . . . . . . . . |
%e A250000 | W W W . . . . . W . . . |
%e A250000 | W W . . . . . W W . . . |
%e A250000 | W . W . . . W W W . . . |
%e A250000 | . W . . . . W W W . . . |
%e A250000 +-------------------------+
%e A250000 A solution for n=13 (from Prestwich/Beck paper):
%e A250000 +---------------------------+
%e A250000 | B . . . B . B . . . B . B |
%e A250000 | . . W . . . . . W . . . . |
%e A250000 | . W . W . W . W . W . W . |
%e A250000 | . . W . . . . . W . . . . |
%e A250000 | B . . . B . B . . . B . B |
%e A250000 | . . W . . . . . W . . . . |
%e A250000 | B . . . B . B . . . B . B |
%e A250000 | . . W . . . . . W . . . . |
%e A250000 | . W . W . W . W . W . W . |
%e A250000 | . . W . . . . . W . . . . |
%e A250000 | B . . . B . B . . . B . B |
%e A250000 | . . W . . . . . W . . . . |
%e A250000 | B . . . B . B . . . B . B |
%e A250000 +---------------------------+
%e A250000 From _Bob Selcoe_, Feb 07 2015: (Start)
%e A250000 An alternative solution for n=13:
%e A250000 +---------------------------+
%e A250000 | . B . B . B . B . B . B . |
%e A250000 | . . B . . . B . . . B . . |
%e A250000 | W . . . W . . . W . . . W |
%e A250000 | . . B . . . B . . . B . . |
%e A250000 | W . . . W . . . W . . . W |
%e A250000 | . . B . . . B . . . B . . |
%e A250000 | W . . . W . . . W . . . W |
%e A250000 | . . B . . . B . . . B . . |
%e A250000 | W . . . W . . . W . . . W |
%e A250000 | . . B . . . B . . . B . . |
%e A250000 | W . . . W . . . W . . . W |
%e A250000 | . . B . . . B . . . B . . |
%e A250000 | W . . . W . . . W . . . W |
%e A250000 +---------------------------+
%e A250000 n=15, a fully symmetrical optimal configuration from _Paul Tabatabai_, Oct 16 2018:
%e A250000 +-------------------------------+
%e A250000 | B . B . B . . . . . B . B . B |
%e A250000 | . . . . . . W W W . . . . . . |
%e A250000 | B . B . B . . . . . B . B . B |
%e A250000 | . . . . . . W . W . . . . . . |
%e A250000 | B . B . . . . . . . . . B . B |
%e A250000 | . . . . . . W . W . . . . . . |
%e A250000 | . W . W . W . W . W . W . W . |
%e A250000 | . W . . . . W . W . . . . W . |
%e A250000 | . W . W . W . W . W . W . W . |
%e A250000 | . . . . . . W . W . . . . . . |
%e A250000 | B . B . . . . . . . . . B . B |
%e A250000 | . . . . . . W . W . . . . . . |
%e A250000 | B . B . B . . . . . B . B . B |
%e A250000 | . . . . . . W W W . . . . . . |
%e A250000 | B . B . B . . . . . B . B . B |
%e A250000 +-------------------------------+
%e A250000 n=17: A 42-queen arrangement (the best presently known) for n=17, from _Rob Pratt_, Feb 07 2014:
%e A250000 +-----------------------------------+
%e A250000 | . . . . W W W W W . . . . . . . . |
%e A250000 | . . . . W W W W W . . . . . . . . |
%e A250000 | . . . . W W W W W . . . . . . . W |
%e A250000 | . . . . W W W W . . . . . . . W W |
%e A250000 | . . . . W W W . . . . . . . W W W |
%e A250000 | . . . . . W . . . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . . W W W . |
%e A250000 | . . . . . . . . . . . . . W W . . |
%e A250000 | . . B B . . . . . . . . . . . . . |
%e A250000 | . B B B . . . . . . . . . . . . . |
%e A250000 | B B B B . . . . . . . . . . . . . |
%e A250000 | B B B B . . . . . . . B . . . . . |
%e A250000 | B B B B . . . . . . B B B . . . . |
%e A250000 | B B B B . . . . . B B B B . . . . |
%e A250000 | B B B . . . . . . B B B B . . . . |
%e A250000 | B B . . . . . . . B B B B . . . . |
%e A250000 +-----------------------------------+
%e A250000 From _Bob Selcoe_, Feb 09 2015: (Start)
%e A250000 Two alternative 42-queen arrangements for n=17 (inspired by _Rob Pratt_). Other arrangements exist.
%e A250000 Alternative 1:
%e A250000 +-----------------------------------+
%e A250000 | . . . . . W W W W W . . . . . . . |
%e A250000 | . . . . . W W W W W . . . . . . . |
%e A250000 | . . . . . W W W W W . . . . . . W |
%e A250000 | . . . . . W W W W . . . . . . W W |
%e A250000 | . . . . . W W W . . . . . . W W W |
%e A250000 | . . . . . . W . . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . . W W W . |
%e A250000 | . . . . . . . . . . . . . W W . . |
%e A250000 | . . . B B . . . . . . . . . . . . |
%e A250000 | . . B B B . . . . . . . . . . . . |
%e A250000 | . B B B B . . . . . . . . . . . . |
%e A250000 | B B B B B . . . . . . B B . . . . |
%e A250000 | B B B B B . . . . . B B B . . . . |
%e A250000 | B B B B . . . . . . B B B . . . . |
%e A250000 | B B B . . . . . . . B B B . . . . |
%e A250000 | B B . . . . . . . . B B B . . . . |
%e A250000 +-----------------------------------+
%e A250000 Alternative 2:
%e A250000 +-----------------------------------+
%e A250000 | . . . . W W W W . . . . . . . . W |
%e A250000 | . . . . W W W W . . . . . . . W W |
%e A250000 | . . . . W W W W . . . . . . W W W |
%e A250000 | . . . . W W W W . . . . . W W W W |
%e A250000 | . . . . . W W . . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . . W W W . |
%e A250000 | . . . . . . . . . . . . . W W . . |
%e A250000 | . . . . . . . . . . . . . W . . . |
%e A250000 | . . B B . . . . . . . . . . . . . |
%e A250000 | . B B B . . . . . . . . . . . . . |
%e A250000 | B B B B . . . . . . . B . . . . . |
%e A250000 | B B B B . . . . . . B B B . . . . |
%e A250000 | B B B . . . . . . B B B B . . . . |
%e A250000 | B B . . . . . . B B B B B . . . . |
%e A250000 | B . . . . . . . B B B B B . . . . |
%e A250000 | . . . . . . . . B B B B B . . . . |
%e A250000 +-----------------------------------+
%e A250000 Example of an alternative n=20, 58-queen arrangement with "cracked" blocks from _Bob Selcoe_, May 23 2017:
%e A250000 +-----------------------------------------+
%e A250000 | . . . . . W W W W W . . . . . . . . W . |
%e A250000 | . . . . . W W W W W . . . . . . . W . W |
%e A250000 | . . . . . W W W W W . . . . . . W . W W |
%e A250000 | . . . . . W W W W W . . . . . W . W W W |
%e A250000 | . . . . . W W W W . . . . . . . W W W W |
%e A250000 | . . . . . W W W . . . . . . . W W W W W |
%e A250000 | . . . . . . W . . . . . . . . W W W W . |
%e A250000 | . . . . . . . . . . . . . . . W W W . . |
%e A250000 | . . . . . . . . . . . . . . . W W . . . |
%e A250000 | . . . . . . . . . W . . . . . W . . . . |
%e A250000 | . . . B B . . . . . . . . . . . . . . . |
%e A250000 | . . B B B . . . . . . . . . . . . . . . |
%e A250000 | . B B B B . . . . . . . . . . . . . . . |
%e A250000 | B B B B B . . . . . . . B . . . . . . . |
%e A250000 | B B B B . . . . . . . B B B . . . . . . |
%e A250000 | B B B . B . . . . . B B B B B . . . . . |
%e A250000 | B B . B . . . . . . B B B B B . . . . . |
%e A250000 | B . B . . . . . . . B B B B B . . . . . |
%e A250000 | . B . . . . . . . . B B B B B . . . . . |
%e A250000 | B . . . . . . . . . B B B B B . . . . . |
%e A250000 +-----------------------------------------+
%e A250000 Pattern for n = 4m; four chessboards total.
%e A250000 Board 1: n=12, a(12)=21:
%e A250000 +-------------------------+
%e A250000 | . . . W W W . . . . . . |
%e A250000 | . . . W W W . . . . . W |
%e A250000 | . . . W W W . . . . W W |
%e A250000 | . . . . W . . . . W W W |
%e A250000 | . . . . . . . . . W W W |
%e A250000 | . . . . . . . . . W W . |
%e A250000 | . . B . . . . . . . . . |
%e A250000 | . B B . . . . . . . . . |
%e A250000 | B B B . . . . . B . . . |
%e A250000 | B B B . . . . B B . . . |
%e A250000 | B B . . . . B B B . . . |
%e A250000 | B . . . . . B B B . . . |
%e A250000 +-------------------------+
%e A250000 Board 2: n=16, 37-queen arrangement:
%e A250000 +---------------------------------+
%e A250000 | . . . . W W W W . . . . . . . . |
%e A250000 | . . . . W W W W . . . . . . . W |
%e A250000 | . . . . W W W W . . . . . . W W |
%e A250000 | . . . . W W W W . . . . . W W W |
%e A250000 | . . . . . W W . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . W W W W |
%e A250000 | . . . . . . . . . . . . W W W . |
%e A250000 | . . . . . . . . . . . . W W . . |
%e A250000 | . . . B . . . . . . . . . . . . |
%e A250000 | . . B B . . . . . . . . . . . . |
%e A250000 | . B B B . . . . . . . . . . . . |
%e A250000 | B B B B . . . . . . B B . . . . |
%e A250000 | B B B B . . . . . B B B . . . . |
%e A250000 | B B B . . . . . B B B B . . . . |
%e A250000 | B B . . . . . . B B B B . . . . |
%e A250000 | B . . . . . . . B B B B . . . . |
%e A250000 +---------------------------------+
%e A250000 Board 3: n=20, 58-queen arrangement:
%e A250000 +-----------------------------------------+
%e A250000 | . . . . . W W W W W . . . . . . . . . . |
%e A250000 | . . . . . W W W W W . . . . . . . . . W |
%e A250000 | . . . . . W W W W W . . . . . . . . W W |
%e A250000 | . . . . . W W W W W . . . . . . . W W W |
%e A250000 | . . . . . W W W W W . . . . . . W W W W |
%e A250000 | . . . . . . W W W . . . . . . W W W W W |
%e A250000 | . . . . . . . W . . . . . . . W W W W W |
%e A250000 | . . . . . . . . . . . . . . . W W W W . |
%e A250000 | . . . . . . . . . . . . . . . W W W . . |
%e A250000 | . . . . . . . . . . . . . . . W W . . . |
%e A250000 | . . . . B . . . . . . . . . . . . . . . |
%e A250000 | . . . B B . . . . . . . . . . . . . . . |
%e A250000 | . . B B B . . . . . . . . . . . . . . . |
%e A250000 | . B B B B . . . . . . . . B . . . . . . |
%e A250000 | B B B B B . . . . . . . B B B . . . . . |
%e A250000 | B B B B B . . . . . . B B B B . . . . . |
%e A250000 | B B B B . . . . . . B B B B B . . . . . |
%e A250000 | B B B . . . . . . . B B B B B . . . . . |
%e A250000 | B B . . . . . . . . B B B B B . . . . . |
%e A250000 | B . . . . . . . . . B B B B B . . . . . |
%e A250000 +-----------------------------------------+
%e A250000 Board 4: n=24, 83-queen arrangement:
%e A250000 +-------------------------------------------------+
%e A250000 | . . . . . . W W W W W W . . . . . . . . . . . . |
%e A250000 | . . . . . . W W W W W W . . . . . . . . . . . W |
%e A250000 | . . . . . . W W W W W W . . . . . . . . . . W W |
%e A250000 | . . . . . . W W W W W W . . . . . . . . . W W W |
%e A250000 | . . . . . . W W W W W W . . . . . . . . W W W W |
%e A250000 | . . . . . . W W W W W W . . . . . . . W W W W W |
%e A250000 | . . . . . . . W W W W . . . . . . . W W W W W W |
%e A250000 | . . . . . . . . W W . . . . . . . . W W W W W W |
%e A250000 | . . . . . . . . . . . . . . . . . . W W W W W . |
%e A250000 | . . . . . . . . . . . . . . . . . . W W W W . . |
%e A250000 | . . . . . . . . . . . . . . . . . . W W W . . . |
%e A250000 | . . . . . . . . . . . . . . . . . . W W . . . . |
%e A250000 | . . . . . B . . . . . . . . . . . . . . . . . . |
%e A250000 | . . . . B B . . . . . . . . . . . . . . . . . . |
%e A250000 | . . . B B B . . . . . . . . . . . . . . . . . . |
%e A250000 | . . B B B B . . . . . . . . . . . . . . . . . . |
%e A250000 | . B B B B B . . . . . . . . . B B . . . . . . . |
%e A250000 | B B B B B B . . . . . . . . B B B B . . . . . . |
%e A250000 | B B B B B B . . . . . . . B B B B B . . . . . . |
%e A250000 | B B B B B . . . . . . . B B B B B B . . . . . . |
%e A250000 | B B B B . . . . . . . . B B B B B B . . . . . . |
%e A250000 | B B B . . . . . . . . . B B B B B B . . . . . . |
%e A250000 | B B . . . . . . . . . . B B B B B B . . . . . . |
%e A250000 | B . . . . . . . . . . . B B B B B B . . . . . . |
%e A250000 +-------------------------------------------------+
%e A250000 (End)
%e A250000 Example of an alternative n=20, 58-queen arrangement with "cracked" blocks from _Bob Selcoe_, May 23 2017:
%e A250000 +-----------------------------------------+
%e A250000 | . . . . . W W W W W . . . . . . . . W . |
%e A250000 | . . . . . W W W W W . . . . . . . W . W |
%e A250000 | . . . . . W W W W W . . . . . . W . W W |
%e A250000 | . . . . . W W W W W . . . . . W . W W W |
%e A250000 | . . . . . W W W W . . . . . . . W W W W |
%e A250000 | . . . . . W W W . . . . . . . W W W W W |
%e A250000 | . . . . . . W . . . . . . . . W W W W . |
%e A250000 | . . . . . . . . . . . . . . . W W W . . |
%e A250000 | . . . . . . . . . . . . . . . W W . . . |
%e A250000 | . . . . . . . . . W . . . . . W . . . . |
%e A250000 | . . . B B . . . . . . . . . . . . . . . |
%e A250000 | . . B B B . . . . . . . . . . . . . . . |
%e A250000 | . B B B B . . . . . . . . . . . . . . . |
%e A250000 | B B B B B . . . . . . . B . . . . . . . |
%e A250000 | B B B B . . . . . . . B B B . . . . . . |
%e A250000 | B B B . B . . . . . B B B B B . . . . . |
%e A250000 | B B . B . . . . . . B B B B B . . . . . |
%e A250000 | B . B . . . . . . . B B B B B . . . . . |
%e A250000 | . B . . . . . . . . B B B B B . . . . . |
%e A250000 | B . . . . . . . . . B B B B B . . . . . |
%e A250000 +-----------------------------------------+
%e A250000 .
%e A250000 n = 24: An 84-queen arrangement found by _Benoit Jubin_, Feb 24 2015 (see Comments above).
%e A250000 +-------------------------------------------------+
%e A250000 | . . . . . . W W W W W W . . . . . . . . . . . . |
%e A250000 | . . . . . . W W W W W W . . . . . . . . . . . W |
%e A250000 | . . . . . . W W W W W W . . . . . . . . . . W W |
%e A250000 | . . . . . . W W W W W W . . . . . . . . . W W W |
%e A250000 | . . . . . . W W W W W W . . . . . . . . W W W W |
%e A250000 | . . . . . . W W W W W . . . . . . . . W W W W W |
%e A250000 | . . . . . . . W W W . . . . . . . . W W W W W W |
%e A250000 | . . . . . . . . W . . . . . . . . . W W W W W W |
%e A250000 | . . . . . . . . . . . . . . . . . . W W W W W W |
%e A250000 | . . . . . . . . . . . . . . . . . . W W W W W . |
%e A250000 | . . . . . . . . . . . . . . . . . . W W W W . . |
%e A250000 | . . . . . . . . . . . . . . . . . . W W W . . . |
%e A250000 | . . . . B B . . . . . . . . . . . . . . . . . . |
%e A250000 | . . . B B B . . . . . . . . . . . . . . . . . . |
%e A250000 | . . B B B B . . . . . . . . . . . . . . . . . . |
%e A250000 | . B B B B B . . . . . . . . . . . . . . . . . . |
%e A250000 | B B B B B B . . . . . . . . . . B . . . . . . . |
%e A250000 | B B B B B B . . . . . . . . . B B B . . . . . . |
%e A250000 | B B B B B B . . . . . . . . B B B B . . . . . . |
%e A250000 | B B B B B . . . . . . . . B B B B B . . . . . . |
%e A250000 | B B B B . . . . . . . . B B B B B B . . . . . . |
%e A250000 | B B B . . . . . . . . . B B B B B B . . . . . . |
%e A250000 | B B . . . . . . . . . . B B B B B B . . . . . . |
%e A250000 | B . . . . . . . . . . . B B B B B B . . . . . . |
%e A250000 +-------------------------------------------------+
%e A250000 .
%e A250000 A solution for n = 27 with 106 queens found by _Dmitry Kamenetsky_, Oct 18 2019
%e A250000 +-------------------------------------------------------+
%e A250000 | . . . . . . . . . . . . W W W W W W W . . . . . . . . |
%e A250000 | . . . . . . . . . . . . W W W W W W W . . . . . . . . |
%e A250000 | W . . . . . . . . . . . W W W W W W W . . . . . . . . |
%e A250000 | W W . . . . . . . . . . W W W W W W W . . . . . . . . |
%e A250000 | W W W . . . . . . . . . W W W W W W W . . . . . . . . |
%e A250000 | W W W W . . . . . . . . . W W W W W W . . . . . . . . |
%e A250000 | W W W W W . . . . . . . . . W W W W W . . . . . . . . |
%e A250000 | W W W W W W . . . . . . . . . W W W . . . . . . . . . |
%e A250000 | W W W W W W . . . . . . . . . . W . W . . . . . . . . |
%e A250000 | W W W W W W . . . . . . . . . . . W . . . . . . . . . |
%e A250000 | W W W W W W . . . . . . . . . . . . . . . . . . . . . |
%e A250000 | . W W W W W . . . . . . . . . . . . . . . . . . . . . |
%e A250000 | . . W W W W . . . . . . . . . . . . . . . . . . . . . |
%e A250000 | . . . W W W . . . . . . . . . . . . . . . . . . . . . |
%e A250000 | . . . . W W . . . . . . W . . . . . . . . . . . . . . |
%e A250000 | . . . . . . . . . . . . . . . . . . . B B B B . . . . |
%e A250000 | . . . . . . . . . . . . . . . . . . . B B B B B . . . |
%e A250000 | . . . . . . . . . . . . . . . . . . . B B B B B B . . |
%e A250000 | . . . . . . . B . . . . . . . . . . . B B B B B B B . |
%e A250000 | . . . . . . B . B . . . . . . . . . . B B B B B B B B |
%e A250000 | . . . . . . . B B B . . . . . . . . . B B B B B B B B |
%e A250000 | . . . . . . B B B B B . . . . . . . . . B B B B B B B |
%e A250000 | . . . . . . B B B B B B . . . . . . . . . B B B B B B |
%e A250000 | . . . . . . B B B B B B . . . . . . . . . . B B B B B |
%e A250000 | . . . . . . B B B B B B . . . . . . . . . . . B B B B |
%e A250000 | . . . . . . B B B B B B . . . . . . . . . . . . B B B |
%e A250000 | . . . . . . B B B B B B . . . . . . . . . . . . . B B |
%e A250000 +-------------------------------------------------------+
%Y A250000 A260680 gives number of solutions.
%Y A250000 Cf. A002620, A274947, A274948, A286283 (lower bound).
%Y A250000 See A000170, A002562, A319284, etc., for the classic non-attacking queens problem.
%Y A250000 See also A279405 (torus version), A176222 (peaceable kings), A002620 (peaceable rooks), A355509 (peaceable knights).
%K A250000 nonn,nice,more
%O A250000 1,4
%A A250000 _Don Knuth_, Aug 01 2014
%E A250000 Uniqueness of n = 5 example corrected by _Rob Pratt_, Nov 30 2014
%E A250000 a(12)-a(13) obtained from Prestwich/Beck paper by _Rob Pratt_, Nov 30 2014
%E A250000 More examples from _Rob Pratt_, Dec 01 2014
%E A250000 a(1)-a(13) confirmed and bounds added for n = 14 to 20 obtained via integer linear programming by _Rob Pratt_, Dec 01 2014
%E A250000 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
%E A250000 Bounds obtained by simulated annealing: a(21) >= 64, a(22) >= 70, a(23) >= 77, a(24) >= 84. - _Peter Karpov_, Apr 03 2016
%E A250000 a(14)-a(15) from _Paul Tabatabai_ using integer programming, Oct 16 2018
%E A250000 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.
%E A250000 Counts for n=4 edited by _N. J. A. Sloane_, Mar 19 2019. See A260680 for more information.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.