A000170 -id:A000170 - cp's OEIS frontend

A319284 The profiles of the backtrack tree for the n queens problem, triangle read by rows.

1, 1, 1, 1, 2, 0, 1, 3, 2, 0, 1, 4, 6, 4, 2, 1, 5, 12, 14, 12, 10, 1, 6, 20, 36, 46, 40, 4, 1, 7, 30, 76, 140, 164, 94, 40, 1, 8, 42, 140, 344, 568, 550, 312, 92, 1, 9, 56, 234, 732, 1614, 2292, 2038, 1066, 352, 1, 10, 72, 364, 1400, 3916, 7552, 9632, 7828, 4040, 724, 1, 11, 90, 536, 2468, 8492, 21362, 37248, 44148, 34774, 15116, 2680

Offset: 0

Peter Luschny, Sep 16 2018

The profile (p_0, p_1, ..., p_n) is the number of nodes at each level of the tree.

			[1]
[1,  1]
[1,  2,  0]
[1,  3,  2,    0]
[1,  4,  6,    4,    2]
[1,  5,  12,  14,   12,    10]
[1,  6,  20,  36,   46,    40,     4]
[1,  7,  30,  76,  140,   164,    94,     40]
[1,  8,  42, 140,  344,   568,   550,    312,     92]
[1,  9,  56, 234,  732,  1614,  2292,   2038,   1066,    352]
[1, 10,  72, 364, 1400,  3916,  7552,   9632,   7828,   4040,    724]
[1, 11,  90, 536, 2468,  8492, 21362,  37248,  44148,  34774,  15116,  2680]
[1, 12, 110, 756, 4080, 16852, 52856, 120104, 195270, 222720, 160964, 68264, 14200]

D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.

Peter Luschny, Rows n = 0..19, flattened
Candida Bowtell and Peter Keevash, The n-queens problem, arXiv:2109.08083 [math.CO] 2021.
V. Kotesovec, Ways of placing non-attacking queens and kings..., part of "Between chessboard and computer", 1996, pp. 204 - 206.
Peter Luschny, Julia implementation of the n queens problem with profiles
Michael Simkin, The number of n-queens configurations, arXiv:2107.13460 [math.CO] 2021.
Wikipedia, Backtracking
Wikipedia, Eight queens puzzle

Cf. A000170 (T(n,n)), A319283 (row sums), A319288 (indices of the row maxima).

Cf. A000012 (col. 0), A000027 (col. 1), A002378 (col. 2), A061989 and A079908 (col. 3), A061990 (col. 4), A061991 (col. 5), A061992 (col. 6), A061993 (col. 7), A172449 (col. 8).

Julia
```
# See the link section.
```

A141843 Triangular array T(n,k) (n >= 1, 1 <= k <= n) read by rows: row n gives the lexicographically earliest solution to the n queens problem, or n zeros if no solution exists. The k-th queen is placed in square (k, T(n, k)).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 2, 4, 1, 3, 1, 3, 5, 2, 4, 2, 4, 6, 1, 3, 5, 1, 3, 5, 7, 2, 4, 6, 1, 5, 8, 6, 3, 7, 2, 4, 1, 3, 6, 8, 2, 4, 9, 7, 5, 1, 3, 6, 8, 10, 5, 9, 2, 4, 7, 1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10, 1, 3, 5, 8, 10, 12, 6, 11, 2, 7, 9, 4, 1, 3, 5, 2, 9, 12, 10

Offset: 1

Colin S. Pearson, Jul 10 2008, Aug 16 2008

History: In December 2017, Matteo Fischetti and Domenico Salvagnin, using Integer Linear Programming (ILP), found solutions for n=56 to n=61; they also found solutions for higher n, but not in contiguous sequence.
Solutions for n=48 to n=55 were found by Wolfram Schubert, around 2010, but not entered in the OEIS.
Entries for board size 46 X 46 (a new solution) and for board size 47 X 47 (already known to Colin Pearson) were added to this sequence in November 2011.
The solution for the 46 X 46 board was discovered by Matthias Engelhardt on Apr 30 2011, the solution for the 47 X 47 board by Colin S. Pearson on Jan 09 2008.
Is it known that the rows converge to (1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, ...) ? - M. F. Hasler, Jan 20 2019.
Comments from Don Knuth, Jul 23 2019: (Start)
(i) Concerning the above question about convergence, note that (a) this is sequence A065188, and (b) such convergence is obvious.
(ii) The new 2019 paper by Fischetti and Salvagnin includes solutions for n = 56-61, 63, 65, 67. 69. 71, 73, 77, 79, 85. 91. 93, 97, 101, 103, 109, 115; so the first unknown case is currently n=62.
(iii) I think this sequence (A141843) ought to be the "archival repository" for progress on this problem (I mean, the lexicographically first solutions to the n queens problem). However, it does not yet include Schubert's previously known solutions for n between 48 and 55. Somebody should now add the Fischetti/Salvagnin results too. Each of these is a significant benchmark example, because it's not easy to prove that a partial n-queens solution cannot be extended.
(iv) Here's an excerpt from a message that Matthias Engelhardt sent me on 30 Oct 2017:
> I do not know of a real paper where it is published; up to know, I
> thought it is contained in the OEIS (Online encyclopedia of integer
> sequences, URL http://oeis.org/A141843), but I detect now that the last
> updates are not done! It was Wolfram Schubert who did
> the last computations, and I thought he would update the OEIS. The
> current entry contains the solutions only to n=47. The result for n=48,
> 54 and 55 were computed by him only, the results for n=46, 50, 51, 52,
> 53 were computed by him and verified with my completely different program.
>
> I know I got the results from Wolfram; unfortunately, I cannot find them
> directly. Implicitly, they are contained in the big GIF image which I
> constructed and which is in the internet under
> http://www.nqueens.de/images/firstAlfa.gif. It is linked on my page
> http://www.nqueens.de/sub/FirstAlfa.en.html (I detected also that I must
> correct a header line there).
>
> I think I should update the OEIS in the next days.
(v) Schubert's result for n=48 hasn't been verified independently, as far as I know. It was too hard for Fischetti and Salvagnin's integer-programming approach, and it's also too hard for my Algorithm X. Maybe a SAT solver would verify it though... .(End)

			Triangle begins:
n\k  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10] [11] [12]
[1]  1;
[2]  0,   0;
[3]  0,   0,   0;
[4]  2,   4,   1,   3;
[5]  1,   3,   5,   2,   4;
[6]  2,   4,   6,   1,   3,   5;
[7]  1,   3,   5,   7,   2,   4,   6;
[8]  1,   5,   8,   6,   3,   7,   2,   4;
[9]  1,   3,   6,   8,   2,   4,   9,   7,   5;
[10] 1,   3,   6,   8,   10,  5,   9,   2,   4,   7;
[11] 1,   3,   5,   7,   9,   11,  2,   4,   6,   8,   10;
[12] 1,   3,   5,   8,   10,  12,  6,   11,  2,   7,   9,   4;
[13] ...
For n=8, the lexicographically smallest solution for the 8-queens problem is 1,5,8,6,3,7,2,4.

Matthias Engelhardt, Table of n, a(n) for n = 1..1892 (previous version of Colin Pearson enlarged)
Matthias R. Engelhardt, The old nQueens problem.
Matteo Fischetti, Domenico Salvagnin, Chasing First Queens by Integer Programming, 2018.
Matteo Fischetti, Domenico Salvagnin, Finding First and Most-Beautiful Queens by Integer Programming, arXiv:1907.08246 [cs.DS], 18 Jul 2019.
Colin S. Pearson, CSP Queens - Counting Queen-placements.
Martin S. Pearson, Queens On A Chessboard.
Wikipedia, Eight Queens Puzzle.

Cf. A065188, A140450, A000170.

row(n)={my(ok(p,a,d)=!for(j=1,n, bittest(d,p[j]-j+n)&& return; bittest(a,p[j]+j)&& return; d+=1<<(p[j]-j+n); a+=1<<(p[j]+j))); for(i=if(n>2,n-3)!*n,n!, ok(numtoperm(n,i))&& return(numtoperm(n,i))); vector(n)} \\ M. F. Hasler, Jan 20 2019

Limit_{n->oo} Sum_{k=1..n} T(n,k)*x^k = A065188(x).

We extended this sequence by adding new terms 1036 to 1128 relating to two further puzzle solutions, for board size 46 X 46 (a new solution) and for board size 47 X 47. Given that the k-th queen is placed in square (k, a(n, k)), we have added the terms (1, a(46, 1)) to (47, a(47, 47)). - Colin S. Pearson, Nov 04 2011

Comments rewritten by Matthias Engelhardt, Jan 28 2018

A189838 Number of ways to place n nonattacking composite pieces rook + rider[2,2] on an n X n chessboard.

Original entry on oeis.org

1, 2, 4, 16, 36, 128, 672, 4264, 25044, 173712, 1318904, 11069056, 96808692, 927478976, 9435033872, 103783608480, 1195155968388

Offset: 1

Vaclav Kotesovec, Apr 29 2011

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

V. Kotesovec, Number of ways of placing non-attacking queens, kings, bishops and knights (in English and Czech)
Wikipedia, Fairy chess piece

Cf. A110128, A000170

A189850 Number of ways to place n nonattacking composite pieces rook + rider[1,3] on an n X n chessboard.

Original entry on oeis.org

1, 2, 6, 8, 24, 126, 316, 1344, 7782, 33930, 172430, 1106754, 6432236, 45188572, 372437930, 2728674526, 23648822368, 233010291526, 2083328647344

Offset: 1

Vaclav Kotesovec, Apr 29 2011

In fairy chess, the rider [1,3] is called a Camelrider.

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

V. Kotesovec, Number of ways of placing non-attacking queens, kings, bishops and knights (in English and Czech)
Wikipedia, Fairy chess piece

Cf. A000170, A189837

A189851 Number of ways to place n nonattacking composite pieces rook + rider[1,4] on an n X n chessboard.

Original entry on oeis.org

1, 2, 6, 24, 48, 182, 868, 5752, 22952, 131766, 912964, 7556978, 52602390, 432795244, 4121203656, 44335718598, 416447624724

Offset: 1

Vaclav Kotesovec, Apr 29 2011

In fairy chess, the rider [1,4] is called a Girafferider.

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

V. Kotesovec, Number of ways of placing non-attacking queens, kings, bishops and knights (in English and Czech)
Wikipedia, Fairy chess piece

Cf. A000170, A189837, A189850

A260318 Number of doubly symmetric characteristic solutions to the n-queens problem.

Original entry on oeis.org

1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 4, 4, 0, 0, 32, 64, 0, 0, 240, 352, 0, 0, 1664, 1632, 0, 0, 16448, 21888, 0, 0, 203392, 333952, 0, 0, 2922752, 4325376, 0, 0, 38592000, 50746368, 0, 0, 630794240, 897616896, 0, 0, 10758713344, 17514086400, 0, 0, 203437559808, 326022221824, 0, 0, 4306790547456, 6265275064320, 0, 0, 97204813266944, 145913049251840, 0, 0

Offset: 1

N. J. A. Sloane, Jul 22 2015

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.

Maurice Kraitchik: Mathematical Recreations. Mineola, NY: Dover, 2nd ed. 1953, pp. 247-255 (The Problem of the Queens).

P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47. [Incomplete annotated scan of title page and pages 18-51]

A002562 = A260318 + A260319 + A260320, A000170 = 2*A260318 + 4*A260319 + 8*A260320 (n>1).

a(n) = A033148(n) / 2 for n >= 2. - Don Knuth, Jun 20 2017

More terms, due to Don Knuth, added by Colin Barker, Jun 20 2017

A260319 Number of singly symmetric characteristic solutions to the n-queens problem.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 1, 4, 3, 12, 18, 32, 105, 310, 734, 2006, 4526, 11046, 36035, 93740, 312673, 895310, 2917938, 8532332, 28929567

Offset: 1

N. J. A. Sloane, Jul 22 2015

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.

Maurice Kraitchik: Mathematical Recreations. Mineola, NY: Dover, 2nd ed. 1953, p. 247-255 (The Problem of the Queens).

P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47. [Incomplete annotated scan of title page and pages 18-51]

A002562 = A260318 + A260319 + A260320, A000170 = 2*A260318 + 4*A260319 + 8*A260320 (n>1).

a(n) = -A000170(n)/4 + 2*A002562(n) - 3*A260318(n)/2, n > 1. - R. J. Mathar, Jul 24 2015

Name edited (by inserting "singly", since "doubly symmetric" solutions are symmetric but not counted here) by Don Knuth, Mar 25 2022

A260320 Number of asymmetric characteristic solutions to the n-queens problem.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 4, 11, 42, 89, 329, 1765, 9197, 45647, 284743, 1846189, 11975869, 83259065, 621001708, 4878630533, 39333230881, 336375931369, 3029241762900, 28439270037332, 275986675209470, 2789712437580722

Offset: 1

N. J. A. Sloane, Jul 22 2015

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.

W. Ahrens, Mathematische Unterhaltungen und Spiele, second edition (1910), see page 231.
Maurice Kraitchik: Mathematical Recreations. Mineola, NY: Dover, 2nd ed. 1953, pp. 247-255 (The Problem of the Queens).

P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47. [Incomplete annotated scan of title page and pages 18-51]

A002562 = A260318 + A260319 + A260320, A000170 = 2*A260318 + 4*A260319 + 8*A260320 (n>1).

a(n) = -A002562(n) + A000170(n)/4 + A260318(n)/2 (n>1). - R. J. Mathar, Jul 24 2015

Offset corrected by Michael Somos, Jun 19 2017

A181499 Triangle read by rows: number of solutions of n queens problem for given n and given number of conflicts.

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 28, 0, 0, 8, 4, 0, 0, 0, 0, 0, 64, 0, 28, 0, 0, 0, 0, 0, 0, 232, 0, 96, 24, 0, 0, 0, 0, 0, 0, 240, 0, 372, 112, 0, 0, 0, 0, 0, 88, 0, 0, 328, 1252, 872, 140, 0, 0, 0, 0, 0, 0, 0, 0, 3016, 5140, 4696, 1316, 32, 0, 0, 0, 0, 0

Offset: 0

Matthias Engelhardt, Oct 25 2010

			For n=4, there are only the two solutions 2-4-1-3 and 3-1-4-2. Both have two conflicts So the terms for n=4 are 0 (0 solutions for n=4 having 0 conflicts), 0, 2 (the two cited above), 0 and 0. These are members 10 to 15 of the sequence.

Matthias Engelhardt, Table of n, a(n) for n = 0..152 (corrected by Michel Marcus, Jan 19 2019)
M. Engelhardt, Conflicts in the n-queens problem
M. Engelhardt, Conflict tables for the n-queens problem
M. R. Engelhardt, A group-based search for solutions of the n-queens problem, Discr. Math., 307 (2007), 2535-2551.

Cf. A000170, A007705, A181500, A181501, A181502.

Row sum = A000170 (number of n queens placements)
Column 0 has same values as A007705 (torus n queens solutions)
Column 1 is always zero.

A181500 Triangle read by rows: number of solutions of n queens problem for given n and given number of queens engaged in conflicts.

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 28, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 64, 0, 28, 0, 0, 0, 0, 0, 0, 232, 8, 32, 48, 32

Offset: 0

Matthias Engelhardt, Oct 30 2010

Schlude and Specker investigate if it is possible to set n-1 non-attacking queens on an n X n toroidal chessboard. That is equivalent to searching for normal (i.e., non-toroidal) solutions of 3 engaged queens. In this case, one of the three queens has conflicts with both other queens. If you remove this queen, you get a setting of n-1 queens without conflicts, i.e., a toroidal solution.

			Triangle begins:
   0;
   1, 0;
   0, 0, 0;
   0, 0, 0, 0;
   0, 0, 0, 0, 2;
  10, 0, 0, 0, 0, 0;
   0, 0, 0, 0, 4, 0,  0;
  28, 0, 0, 0, 0, 0, 12, 0;
... - _Andrew Howroyd_, Dec 31 2017
For n=4, there are only the two solutions 2-4-1-3 and 3-1-4-2. For both solutions, all 4 queens are engaged in conflicts. So the terms for n=4 are 0 (0 solutions for n=4 having 0 engaged queens), 0, 0, 0 and 2 (the two cited above). These are members 11 to 15 of the sequence.

M. Engelhardt, Rows n=0..16 of triangle, flattened
Matthias Engelhardt, Conflicts in the n-queens problem
Matthias Engelhardt, Conflict tables for the n-queens problem
M. R. Engelhardt, A group-based search for solutions of the n-queens problem, Discr. Math., 307 (2007), 2535-2551.
Konrad Schlude and Ernst Specker, Zum Problem der Damen auf dem Torus, Technical Report 412, Computer Science Department ETH Zurich, 2003.

Cf. A181499, A181501, A181502.

Row sum = A000170 (number of n-queen placements).
Column 0 has same values as A007705 (torus n-queen solutions).
Columns 1 and 2 are always zero.
Column 3 counts solutions of the special "Schlude-Specker" situation.

Offset corrected by Andrew Howroyd, Dec 31 2017

cp's OEIS Frontend

A319284 The profiles of the backtrack tree for the n queens problem, triangle read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

A141843 Triangular array T(n,k) (n >= 1, 1 <= k <= n) read by rows: row n gives the lexicographically earliest solution to the n queens problem, or n zeros if no solution exists. The k-th queen is placed in square (k, T(n, k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A189838 Number of ways to place n nonattacking composite pieces rook + rider[2,2] on an n X n chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

A189850 Number of ways to place n nonattacking composite pieces rook + rider[1,3] on an n X n chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

A189851 Number of ways to place n nonattacking composite pieces rook + rider[1,4] on an n X n chessboard.

Views

Author

Keywords

Comments

Links

Crossrefs

A260318 Number of doubly symmetric characteristic solutions to the n-queens problem.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A260319 Number of singly symmetric characteristic solutions to the n-queens problem.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A260320 Number of asymmetric characteristic solutions to the n-queens problem.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A181499 Triangle read by rows: number of solutions of n queens problem for given n and given number of conflicts.

Views

Author

Keywords

Examples