cp's OEIS Frontend

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

Analog of A269526, but note that this is a right triangle.

The same rule applied to an equilateral triangle gives A269526.

We construct the triangle by reading from left to right in each row, starting with T(1,1) = 1.

Presumably every diagonal and every column is also a permutation of the positive integers, but the proof does not seem so straightforward. Of course, neither the rows nor the antidiagonals are permutations of the positive integers, since they are finite in length.

Omar E. Pol's conjecture that every column and every diagonal of the triangle is a permutation of the positive integers is true: see the link in A274650 (duplicated below). - N. J. A. Sloane, Jun 07 2017

It appears that the numbers generally appear for the first time in or near the right border of the triangle.

Theorem 1: the middle diagonal gives A000012 (the all 1's sequence).

Theorem 2: all 1's are in the middle diagonal.

For the proofs of the theorems 1 and 2 see the proofs of the theorems 1 and 2 of A274650 since both sequences are essentially the same.

From Bob Selcoe, Feb 15 2017: (Start)

The columns and diagonal are permutations of the natural numbers. The proofs are essentially the same as the proofs given for the columns and rows (respectively) in A269526.

All coefficients j <= 4 eventually populate in a repeating pattern toward the "middle diagonal" (i.e., relatively near the 1's); this is because we can build the triangle by j in ascending order; that is, we can start by placing all the 1's in the proper cells, then add the 2's, 3's, 4's, 5's, etc. So for i >= 0: since the 1's appear at T(1+2i, 1+i), the 2's appear at T(2+8i, 1+4i), T(3+8i, 3+4i), T(5+8i, 2+4i) and T(6+8i, 4+4i). Accordingly, after the first five 3's appear (at T(2,2), T(4,1), T(5,4), T(7,3) and T(8,6)), the remaining 3's appear at T(11+8i, 5+4i), T(12+8i, 7+4i), T(16+8i, 8+4i) and T(17+8i, 10+4i). Similarly for 4's, after the first 21 appearances, 4's appear at T(44+8i, 21+4i), T(45+8i, 24+4i), T(47+8i, 23+4i) and T(48+8i, 26+4i). So starting at T(41,21), this 16-coefficient pattern repeats at T(41+8i, 21+4i):

n/k 21 22 23 24 25 26

41 1 3

42 2

43 3 1 2

44 4 3

45 2 1 4

46 2

47 4 1

48 3 4

where the next 1 appears at T(49,25), and the pattern repeats at that point from the top left (so T(49,26) = 3, T(50,25) = 2, etc.).

Conjecture: as n gets sufficiently large, all coefficients j>4 will appear in a repeating pattern, populating all rows and diagonals around smaller j's near the "middle diagonal" (while I can offer no formal proof, it appears very likely that this is the case). (End)

From Hartmut F. W. Hoft, Jun 12 2017: (Start)

T(2k+1,k+1) = 1, for all k>=0, and T(n,{n/2,(n+3)/2,(n-1)/2,(n+2)/2}) = 2, for all n>=1 with mod(n,8) = {2,3,5,6} respectively, and no 1's or 2's occur in other positions.

Proof by (recursive) picture:

Positions in the triangle that are empty and those containing the dots of the guiding diagonals contain numbers larger than two.

n\k 1 2 3 4 5 6 7 8 10 12 14 16 18 20 22 24

1 |1

2 |2 .

3 | 1 2

4 | .

5 | 2 1 .

6 | 2 .

7 | 1 .

8 |____________.

9 | |1 .

10 | |2 . .

11 | | 1 2 .

12 | | . .

13 | | 2 1 . .

14 | | 2 . .

15 | | 1 . .

16 |_____|______________._____.

17 | | |1 . .

18 | | |2 . . .

19 | | | 1 2 . .

20 | | | . . .

21 | | | 2 1 . . .

22 | | | 2 . . .

23 | | | 1 . . .

24 |_____|_______|____._______._____._______.

1 2 3 4 5 6 7 8 12 16 20 24

Consider the center of the triangle. In each octave of rows the columns in the first central quatrain contain a 1 and a 2, and the diagonals in the second central quatrain contain a 1 and a 2. Therefore, no 1's or 2's can occur in the respective downward quatrains of leading columns and trailing diagonals.

The sequence of rows containing 2's is A047447 (n mod 8 = {2,3,5,6}), those containing only 2's is A016825 (n mod 8 = {2,6}), those containing both 1's and 2's is A047621 (n mod 8 = {3,5}), those containing only 1's is A047522 (n mod 8 = {1,7}), and those containing neither 1's nor 2's is A008586 (n mod 8 = {0,4}).

(End)

The sequence has been computed up to n = 23 by Rivin, Vardi & Zimmermann, see p. 637 of their paper from 1994. Further terms were calculated by the submitter, Dec 17 1999 and Jan 11 2001.

a(n) is divisible by n.

Only terms indexed by odd numbers coprime to 3 are nonzero, therefore A007705(n) = a(2n+1) is the main entry. - M. F. Hasler, Jul 01 2019

From Eduard I. Vatutin, Nov 27 2023: (Start)

For n <= 11 all solutions can be found using a knight moving with some displacements dx and dy starting from some cell with coordinates (x,y): (x,y) -> (x+dx,y+dy) -> (x+2*dx,y+2*dy) -> ... -> (x,y) (all operations modulo n). For n >= 13 some solutions are same, but not all (see examples).

All solutions of n-queens problem on toroidal chessboard are also solutions of n-queens problem on classical chessboard; the converse is not true, so a(n) <= A000170(n).

(End)

A Queen of the Night can move like a Queen or a Nightrider, which is a rider along straight lines of Knight moves.

This sequence was mentioned by R. K. Guy in the first comment in A004396.

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)

All the permutations A004515 and A065256-A065258 consist of the first fixed term ("Queen on the corner") plus infinitely many 4-cycles and they satisfy the "nonattacking queen condition" that p(i+d) <> p(i)+-d for all i and d >= 1.

The corresponding infinite permutation matrix is a scale-invariant fractal (cf. A048647) and any subarray (5^i) X (5^i) (i >= 1) cut from its corner gives a solution to the case n=5^i of the n nonattacking queens on n X n chessboard (A000170). Is there any permutation of N which would give solutions to the queen problem with more frequent intervals than A000351?

(In fairy chess the rider [1,2] is called a Nightrider, Rook + Nightrider = Waran.)

a(n) is also the number of permutations p of 1,2,...,n satisfying |p(i+k) - p(i)| <> 2k AND |p(j+2k) - p(j)| <> k for all i >= 1, j >= 1, k >= 1, i+k <= n, j+2k <= n.