cp's OEIS Frontend

Intuitively this is the level in the backtrack tree of the n queens problem where the algorithm spends more time than on any other level.

The constraint 'is the smallest' in the name can be dropped if the profile of the backtrack tree of the n queens problem is unimodal (for n>1).

The corresponding maxima are: 1, 1, 2, 3, 6, 14, 46, 164, 568, 2292, 9632, 44148, 222720, 1151778, 6471872, 39290462, 260303408, 1812613348, 13308584992, 102670917500.

For n > 3, a(n) is the number of maximum independent vertex sets in the n X n queen graph. - Eric W. Weisstein, Jun 20 2017

Number of nodes on level n of the backtrack tree for the n queens problem (a(n) = A319284(n, n)). - Peter Luschny, Sep 18 2018

Number of permutations of [1...n] such that |p(j)-p(i)| != j-i for iXiangyu Chen, Dec 24 2020

M. Simkin shows that the number of ways to place n mutually nonattacking queens on an n X n chessboard is ((1 +/- o(1))*n*exp(-c))^n, where c = 1.942 +/- 0.003. These are approximately (0.143*n)^n configurations. - Peter Luschny, Oct 07 2021

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