cp's OEIS Frontend

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

A superqueen moves like a queen and a knight.

Superqueens are also called amazons.

From Don Knuth, Jul 17 2015: (Start)

Ahrens proved that a(n)=0 unless n=4k or 4k+1. He also proved that in the latter case, a(n) is a multiple of 2^k. He found all solutions when n was less than 20.

Kraitchik carried the calculations further (for n less than 28). In his book he tabulated only the values a(n)/2^k. He had correct entries for n=21 and n=25, but his values for n=20 and n=24 were 1 too small -- of course he had calculated everything by hand! (End)

The problem of placing eight queens on a chessboard so that no one of them can take any other in a single move is a particular case of the more general problem: On a square array of n X n cells place n objects, one on each of n different cells, in such a way that no two of them lie on the same row, column, or diagonal.

There are no (interesting) doubly centrosymmetric solutions for n < 4, and there is just one complete set for n = 4: 2413, 3142 and one for n = 5: 25314, 41352.

On the ordinary chessboard of 8 X 8 cells there are a total of 92 solutions, consisting of 11 sets of equivalent ordinary solutions and one set of equivalent symmetric solutions. There are no doubly symmetric solutions in this case.

The problem of placing eight queens on a chessboard so that no one of them can take any other in a single move is a particular case of the more general problem: On a square array of n X n cells place n objects, one on each of n different cells, in such a way that no two of them lie on the same row, column, or diagonal.

There are no centrosymmetric solutions for n < 6, if by "centrosymmetric" we exclude "doubly symmetric" cases; and there is just one complete set for n = 6: 246135, 362514, 415263, 531642.

On the ordinary chessboard of 8 X 8 cells there are a total of 92 solutions, consisting of 11 sets of equivalent ordinary solutions and one set of equivalent symmetric solutions. There are no doubly symmetric solutions in this case. These sets may be generated in the ordinary case by 15863724, 16837425, 24683175, 2571384, 25741863, 26174835, 26831475, 27368514, 27581463, 35841726, 36258174 and in the symmetric case by 35281746.

The problem of placing eight queens on a chessboard so that no one of them can take any other in a single move is a particular case of the more general problem: On a square array of n X n cells place n objects, one on each of n different cells, in such a way that no two of them lie on the same row, column, or diagonal.

There are no ordinary solutions for n < 5, and there is just one complete set of ordinary solutions for n = 5: 13524, 52413, 24135, 35241, 53142, 14253, 42531, 31425 (generated by reflection and rotation).

On the ordinary chessboard of 8 X 8 cells there are a total of 92 solutions, consisting of 11 sets of equivalent ordinary solutions and one set of equivalent symmetric solutions. There are no doubly symmetric solutions in this case. These sets may be generated in the ordinary case by 15863724, 16837425, 24683175, 2571384, 25741863, 26174835, 26831475, 27368514, 27581463, 35841726, 36258174 and in the symmetric case by 35281746.

In this sequence two n-queens solutions p and q are considered equivalent iff there are natural numbers x and y such that, for all k from {0, ..., n-1}, q (k + x mod n) = p (k) + y mod n, or q is a rotation or a reflection of such a q.

In other words, besides rotations and reflections, also torus shifts are allowed. The sequence reduces the objects of A002562 and via that of A000170. The reduction of A000170 to this sequence is exactly the same as from A007705 to A053994 for torus queens; however, a solution for torus queens remains always a solution after a shift while a normal queens solutions does so only sometimes.

Note that the equivalence classes of this sequence are a subset of A006841. Moreover they are a subset of A062167.