A061989 -id:A061989 - 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.
```

A172201 Number of ways to place 3 nonattacking amazons (superqueens) on an n X n board.

Original entry on oeis.org

0, 0, 0, 0, 48, 424, 1976, 6616, 17852, 41544, 86660, 166288, 298616, 508200, 827168, 1296744, 1968676, 2907016, 4189772, 5910944, 8182400, 11136168, 14926536, 19732600, 25760588, 33246664, 42459476, 53703216, 67320392, 83695144

Offset: 1

Vaclav Kotesovec, Jan 29 2010

An amazon (superqueen) moves like a queen and a knight.

Panos Louridas, idee & form 93/2007, pp. 2936-2938.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (5,-8,0,14,-14,0,8,-5,1).

Cf. A047659, A051223, A051224, A061989, A172200.

R:=PowerSeriesRing(Integers(), 40); [0,0,0,0] cat Coefficients(R!( 4*x^5*(12+46*x+60*x^2+32*x^3-23*x^4-13*x^5+7*x^6-x^7)/((1+x)^2*(1-x)^7 ))); // G. C. Greubel, Apr 29 2022

CoefficientList[Series[4*x^5*(12+46*x+60*x^2+32*x^3-23*x^4-13*x^5+7*x^6-x^7)/((1+x)^2*(1-x)^7), {x, 0, 40}], x] (* Vincenzo Librandi, May 27 2013 *)

[(1/24)*(4*n^6 -40*n^5 +62*n^4 +628*n^3 -2904*n^2 +4074*n -1341 +3*(-1)^n*(2*n-1)) -4*(5*bool(n==1) +2*bool(n==2) -bool(n==3)) for n in (1..40)] # G. C. Greubel, Apr 29 2022

Explicit formula (Panos Louridas, 2007): a(n) = (2*n^6 - 20*n^5 + 31*n^4 + 314*n^3 - 1452*n^2 + 2040*n - 672)/12 if n is even (n >= 4) and a(n) = (2*n^6 - 20*n^5 + 31*n^4 + 314*n^3 - 1452*n^2 + 2034*n - 669)/12 if n is odd (n >= 5).
G.f.: 4*x^5*(12+46*x+60*x^2+32*x^3-23*x^4-13*x^5+7*x^6-x^7)/((1+x)^2*(1-x)^7). - Vaclav Kotesovec, Mar 24 2010
a(n) = (1/24)*(4*n^6 - 40*n^5 + 62*n^4 + 628*n^3 - 2904*n^2 + 4074*n - 1341 + 3*(-1)^n*(2*n-1)) - 20*[n=1] - 8*[n=2] + 4*[n=3]. - G. C. Greubel, Apr 29 2022

A172207 Number of ways to place 3 nonattacking bishops on a 3 X n board.

Original entry on oeis.org

1, 6, 26, 86, 211, 426, 758, 1234, 1881, 2726, 3796, 5118, 6719, 8626, 10866, 13466, 16453, 19854, 23696, 28006, 32811, 38138, 44014, 50466, 57521, 65206, 73548, 82574, 92311, 102786, 114026, 126058, 138909, 152606, 167176, 182646, 199043, 216394, 234726, 254066

Offset: 1

Vaclav Kotesovec, Jan 29 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A172124, A061989, A047659, A061996.

CoefficientList[Series[(2 x^6 + 14 x^3 + 8 x^2 + 2 x + 1) / (x - 1)^4, {x, 0, 50}], x] (* Vincenzo Librandi, May 27 2013 *)

a(n) = (9n^3 - 45n^2 + 106n - 108)/2, n>=4.

G.f.: x*(2*x^6+14*x^3+8*x^2+2*x+1)/(x-1)^4. - Vaclav Kotesovec, Mar 25 2010

A172221 Number of ways to place 3 nonattacking zebras on a 3 X n board.

Original entry on oeis.org

1, 20, 84, 200, 403, 720, 1180, 1808, 2631, 3676, 4970, 6540, 8413, 10616, 13176, 16120, 19475, 23268, 27526, 32276, 37545, 43360, 49748, 56736, 64351, 72620, 81570, 91228, 101621, 112776, 124720, 137480, 151083, 165556, 180926, 197220

Offset: 1

Vaclav Kotesovec, Jan 29 2010

Zebra is a (fairy chess) leaper [2,3].

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Eric Weisstein's World of Mathematics, Zebra Graph
Wikipedia, Zebra (chess)

Cf. A172138, A061989.

CoefficientList[Series[(2 x^8 - 4 x^7 + 2 x^6 - 8 x^5 + 28 x^4 - 20 x^3 + 10 x^2 + 16 x + 1) / (x - 1)^4, {x, 0, 50}], x] (* Vincenzo Librandi, May 28 2013 *)

a(n) = (9*n^3 - 21*n^2 + 50*n - 48)/2, n>=6.

G.f.: x*(2*x^8-4*x^7+2*x^6-8*x^5+28*x^4-20*x^3+10*x^2+16*x+1)/(x-1)^4. - Vaclav Kotesovec, Mar 25 2010

More terms from Vincenzo Librandi, May 28 2013

A172449 Number of ways to place 8 nonattacking queens on an 8 X n board.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 92, 1066, 7828, 44148, 195270, 707698, 2211868, 6120136, 15324708, 35312064, 75937606, 153942964, 296590536, 546621416, 968910732, 1659114170, 2754780934, 4449361442, 7009572728, 10796663102, 16292133888

Offset: 1

Vaclav Kotesovec, Feb 03 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes

Cf. A061989, A061990, A061991, A061992, A061993.

CoefficientList[Series[x^7 (-72 x^31 + 360 x^30 - 360 x^29 - 1320 x^28 + 4208 x^27 - 9064 x^26 + 28358 x^25 - 65290 x^24 + 80160 x^23 - 41550 x^22 - 19482 x^21 + 62314 x^20 - 43912 x^19 - 81620 x^18 + 228424 x^17 - 261720 x^16 + 248114 x^15 - 336290 x^14 + 460564 x^13 - 453438 x^12 + 288474 x^11 - 135252 x^10 + 80270 x^9 - 85476 x^8 + 49676 x^7 - 23614 x^6 - 4768 x^5 - 1794 x^4 - 4344 x^3 - 1546 x^2 - 238 x - 92) / (x - 1)^9, {x, 0, 50}], x] (* Vincenzo Librandi, May 29 2013 *)

a(n) = n^8 - 84*n^7 + 3378*n^6 - 85078*n^5 + 1467563*n^4 - 17723656*n^3 + 145910074*n^2 - 745654756*n + 1802501048, for n >= 31. - Vaclav Kotesovec, Feb 03 2010

G.f.: x^8*(-72*x^31 + 360*x^30 - 360*x^29 - 1320*x^28 + 4208*x^27 - 9064*x^26 + 28358*x^25 - 65290*x^24 + 80160*x^23 - 41550*x^22 - 19482*x^21 + 62314*x^20 - 43912*x^19 - 81620*x^18 + 228424*x^17 - 261720*x^16 + 248114*x^15 - 336290*x^14 + 460564*x^13 - 453438*x^12 + 288474*x^11 - 135252*x^10 + 80270*x^9 - 85476*x^8 + 49676*x^7 - 23614*x^6 - 4768*x^5 - 1794*x^4 - 4344*x^3 - 1546*x^2 - 238*x - 92)/(x-1)^9. - Vaclav Kotesovec, Mar 20 2010

A172218 Number of ways to place 3 nonattacking nightriders on a 3 X n board.

Original entry on oeis.org

1, 12, 36, 100, 213, 408, 712, 1148, 1745, 2528, 3524, 4760, 6263, 8060, 10178, 12644, 15485, 18728, 22400, 26528, 31139, 36260, 41918, 48140, 54953, 62384, 70460, 79208, 88655, 98828, 109754, 121460, 133973, 147320, 161528, 176624, 192635

Offset: 1

Vaclav Kotesovec, Jan 29 2010

A nightrider is a fairy chess piece that can move (proportionate to how a knight moves) in any direction.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes

Cf. A172141, A061989, A172212.

CoefficientList[Series[(2 x^10 - 4 x^9 + 6 x^8 - 4 x^7 - 6 x^6 + 24 x^5 - 18 x^4 + 24 x^3 - 6 x^2 + 8 x + 1) / (x - 1)^4, {x, 0, 50}], x] (* Vincenzo Librandi, May 28 2013 *)

a(n) = (9n^3 - 57n^2 + 210n - 344)/2, n>=8.

G.f.: x*(2*x^10-4*x^9+6*x^8-4*x^7-6*x^6+24*x^5-18*x^4+24*x^3-6*x^2+8*x+1)/(x-1)^4. - Vaclav Kotesovec, Mar 25 2010

A248944 T(n,k)=Number of length n arrays x(i), i=1..n with x(i) in i..i+k and no value appearing more than 1 time.

Original entry on oeis.org

2, 3, 3, 4, 7, 4, 5, 13, 14, 5, 6, 21, 36, 26, 6, 7, 31, 76, 90, 46, 7, 8, 43, 140, 246, 212, 79, 8, 9, 57, 234, 566, 738, 478, 133, 9, 10, 73, 364, 1146, 2104, 2108, 1044, 221, 10, 11, 91, 536, 2106, 5150, 7364, 5794, 2227, 364, 11, 12, 111, 756, 3590, 11196, 21652, 24720

Offset: 1

R. H. Hardin, Oct 17 2014

Table starts
..2...3....4......5......6.......7........8........9........10........11
..3...7...13.....21.....31......43.......57.......73........91.......111
..4..14...36.....76....140.....234......364......536.......756......1030
..5..26...90....246....566....1146.....2106.....3590......5766......8826
..6..46..212....738...2104....5150....11196....22162.....40688.....70254
..7..79..478...2108...7364...21652....55532...127604....268108....523244
..8.133.1044...5794..24720...86608...260720...693552...1666000...3675680
..9.221.2227..15458..80196..334072..1173240..3598120...9856552..24553080
.10.364.4664..40296.253072.1249768..5112544.17990600..56010096.157175032
.11.596.9627.103129.780902.4557284.21670160.87396728.308055528.971055240

R. H. Hardin, Table of n, a(n) for n = 1..507

Column 1 is A000027(n+1)
Column 2 is A001924(n+1)
Column 3 is A079922
Column 4 is A079923
Column 5 is A079924
Column 6 is A079925
Column 7 is A079926
Row 1 is A000027(n+1)
Row 2 is A002061(n+1)
Row 3 is A061989(n+3)
Row 4 is A079909
Row 5 is A079910
Row 6 is A079911
Row 7 is A079912

Empirical for column k:
k=1: a(n) = 2*a(n-1) -a(n-2)
k=2: a(n) = 3*a(n-1) -2*a(n-2) -a(n-3) +a(n-4)
k=3: a(n) = 4*a(n-1) -4*a(n-2) -2*a(n-4) +4*a(n-5) -a(n-8)
k=4: [order 16]
k=5: [order 32]
k=6: [order 63]
Empirical for row n:
n=1: a(n) = n + 1
n=2: a(n) = n^2 + n + 1
n=3: a(n) = n^3 + 3*n
n=4: a(n) = n^4 - 2*n^3 + 9*n^2 - 8*n + 6 for n>1
n=5: a(n) = n^5 - 5*n^4 + 25*n^3 - 55*n^2 + 80*n - 46 for n>1
n=6: a(n) = n^6 - 9*n^5 + 60*n^4 - 225*n^3 + 555*n^2 - 774*n + 484 for n>3
n=7: a(n) = n^7 - 14*n^6 + 126*n^5 - 700*n^4 + 2625*n^3 - 6342*n^2 + 9072*n - 5840 for n>4

A269133 Number of ways to place m nonattacking queens on an m X n board, 1 <= m <= n (triangular array).

Original entry on oeis.org

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

Offset: 1

Marko Riedel, Feb 19 2016

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

Math StackExchange, State space for eight queen problem
Marko Riedel, Perl program to compute triangular array of nonattacking queens configurations

Cf. A000170 (m=n), A002562, A065256, A348129.
Cf. A000027 (m=1), A002378 (m=2), A061989 (m=3), A061990 (m=4), A061991 (m=5), A061992 (m=6), A061993 (m=7), A172449 (m=8).
Cf. A036464 (2Q), A047659 (3Q), A061994 (4Q), A108792 (5Q), A176186 (6Q).
Cf. A006717, A051906, A319284 (backtrack trees).

{A269133(m, n, B=[], t=if(#B, setminus(n, Set(concat(B+t=[-#B..-1], B-t))), n=[1..n]))= if(#B < m-1, vecsum([A269133(m, setminus(n, [t]), concat(B,t)) | t<-t]), #t)} \\ M. F. Hasler, Jan 11 2022

A137279 Number of ways of placing ceiling(n/2) nonattacking queens on an n X n Mobius chessboard.

Original entry on oeis.org

1, 4, 0, 16, 40, 192, 560, 3328, 11772, 63840, 259336, 1550976, 7169656, 42410256, 234044160, 1366190592

Offset: 1

Brett Stevens (brett(AT)math.carleton.ca), Mar 13 2008

The chessboard is an n X n standard chessboard whose left and right edges are twisted connected.

			a(4)=16 because any queen attacks all but two other squares and every solution is counted twice by enumerating all such placements.

J. Bell and B. Stevens, Results for the n-queens problem on the Mobius board, Australasian Journal of Combinatorics, vol.42, p.21 (2008).

Cf. A000170, A007705, A002562, A053994, A061989, A061990.

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

A172201 Number of ways to place 3 nonattacking amazons (superqueens) on an n X n board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A172207 Number of ways to place 3 nonattacking bishops on a 3 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A172221 Number of ways to place 3 nonattacking zebras on a 3 X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A172449 Number of ways to place 8 nonattacking queens on an 8 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A172218 Number of ways to place 3 nonattacking nightriders on a 3 X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A248944 T(n,k)=Number of length n arrays x(i), i=1..n with x(i) in i..i+k and no value appearing more than 1 time.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A269133 Number of ways to place m nonattacking queens on an m X n board, 1 <= m <= n (triangular array).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs