A002562 -id:A002562 - cp's OEIS frontend

A103331 Number of ways to place n+1 queens and a pawn on an n X n board so that no two queens attack each other (symmetric solutions count only once).

0, 0, 0, 0, 0, 2, 3, 16, 52, 286, 1403, 8214, 54756, 389833, 2923757, 22932960, 184339572

Offset: 1

R. Douglas Chatham (d.chatham(AT)moreheadstate.edu), Jan 31 2005

			For n=6 the a(6)=2 solutions are
 . . Q . . .    . . Q . . .
 Q . P . . Q    Q . P . . Q
 . . . Q . .    . . Q . . .
 . Q . . . .    . . . . Q .
 . . . . Q .    . Q . . . .
 . . Q . . .    . . . Q . .

R. D. Chatham, The N+k Queens Problem Page.
R. D. Chatham, G. H. Fricke and R. D. Skaggs, The Queens Separation Problem, Utilitas Mathematica 69 (2006), 129-141.
R. D. Chatham, M. Doyle, G. H. Fricke, J. Reitmann, R. D. Skaggs and M. Wolff, Indepe ndence and Domination Separation in Chessboard Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, to appear.

Cf. A103330, A002562, A368061.

More terms from R. Douglas Chatham (d.chatham(AT)moreheadstate.edu), Feb 15 2005, Apr 20 2007

A140450 The count of how many queens must be placed tentatively onto a board while seeking a first solution to the "N-Queens on an N x N chessboard" puzzle.

Original entry on oeis.org

1, 6, 18, 26, 15, 171, 42, 876, 333, 975, 517, 3066, 1365, 26495, 20280, 160712, 91222, 743229, 48184, 3992510, 179592, 38217905, 584591, 9878316, 1216775, 10339849, 12263400, 84175966, 44434525, 1692888135, 408773285, 2799725104, 4618568460

Offset: 1

Colin S. Pearson and Martin S. Pearson, Jun 26 2008, Jun 30 2008, Jul 03 2008, Jul 31 2008, Aug 16 2008

nonn

The term a(4) with the value 26 is the count for a board size of 4 squares by 4 squares. The highest term so far a(45) is the count for a board of 45 squares by 45 squares.

This whole sequence refers only to the number of queen pieces placed tentatively on a board in the hunt for the FIRST POSSIBLE solution for each board size. This sequence makes no reference to queen placements needed to hunt for subsequent solutions that are possible for board sizes above 3x3.

			Using a simple, mechanical and naive "one queen at a time" algorithm (in other words, a computer-friendly algorithm), in order to place 4 non-clashing queens on a simple board of 4 x 4 squares, we will need to place a tentative new queen 26 times before we discover the first combination that allows all queens to sit unchallenged. For a board size of 5 x 5 we will need to place tentative new queens just 15 times before we discover the first combination of 5 unchallenged queens. In this extended and corrected sequence, those figures "26" and "15" are the values of terms a(4) and a(5) above.

CSP Queens - Counting Queen-placements http://queens.cspea.co.uk/

Colin S. Pearson, Table of n, a(n) for n = 1..45 [Corrected Jul 31 2008]
Colin S. Pearson, CSP Queens - Counting Queen-placements
Martin S. Pearson, Queens On A Chessboard
Wikipedia, Eight Queens puzzle

Cf. A000170 = Number of ways of placing n nonattacking queens on n X n board; A002562 = Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once); A141843 = Triangular array of lexicographically earliest solutions to the n queens problem.

Edited by Colin S Pearson to update the URL for Martin S Pearson's website Colin S. Pearson, Mar 25 2009

A218244 Number of inequivalent (rotationally and reflectively distinct) ways to place n nonattacking empresses on n X n board.

Original entry on oeis.org

1, 1, 1, 3, 6, 21, 75, 415, 2621, 21066, 195485, 2083543, 24744474, 323438322, 4596672672, 70440521310

Offset: 1

Witold Dlugosz, Oct 24 2012

An empress moves like a rook and a knight.

			a(4) = 3: different ways to place 4 nonattacking empresses on a 4 X 4 board:
Xooo Xooo oXoo
oXoo oooX Xooo
ooXo ooXo oooX
oooX oXoo ooXo

V. Kotesovec, Non-attacking chess pieces

Cf. A137774, A002562.

A062165 Number of ways of placing n nonattacking (normal) queens on n X n board, solutions similar on the torus count only once.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 3, 4, 13, 36, 115, 813, 3083, 21001, 131859, 868613

Offset: 1

Matthias Engelhardt

Two n-queens solutions p and q are considered similar iff there is a factor f, 0 < f < n, satisfying gcd (f,n) = 1, such that for all k from {0, ..., n-1} q (k * f mod n) = p (k) * f mod n or q is a rotation, a reflection or a shift of such a q. In other words, also expansions are allowed which move the queen at (k, p(k)) to (f * k mod n, f * p(k) mod n).

The sequence reduces exactly the objects of A062164 and, via that sequence, these of A002562 and A000170. Note that the equivalence classes of this sequence are a subset of A062168.

M. Engelhardt, The N queens problem

Updated link that is transferred from people.freenet.de/nQueens to www.nqueens.de Matthias Engelhardt, Apr 21 2010

A129552 Number of ways to place n+2 queens and 2 pawns on an n X n board so that no two queens attack each other (symmetric solutions count only once).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 6, 37, 164, 1572, 13133, 122279, 1155103, 11347863, 112182378

Offset: 1

R. Douglas Chatham (d.chatham(AT)moreheadstate.edu), Apr 20 2007

			a(4)=0 because when 6 queens are placed on a 4 X 4 board, at least two queens will be adjacent and therefore mutually attacking.

R. D. Chatham, The N+k Queens Problem Page.
R. D. Chatham, M. Doyle, G. H. Fricke, J. Reitmann, R. D. Skaggs and M. Wolff, Independence and Domination Separation in Chessboard Graphs, J. Combin. Math. Combin. Comput. 68 (2009), 3-17.

Cf. A002562, A129551.

A129554 Number of ways to place n+3 queens and 3 pawns on an n X n board so that no two queens attack each other (symmetric solutions count only once).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 6, 66, 751, 9737, 131672, 1708295

Offset: 1

R. Douglas Chatham (d.chatham(AT)moreheadstate.edu), Apr 20 2007

			a(4)=0 because when 7 queens are placed on a 4 X 4 board, at least two queens will be adjacent and therefore mutually attacking.

R. D. Chatham, The N+k Queens Problem Page.
R. D. Chatham, M. Doyle, G. H. Fricke, J. Reitmann, R. D. Skaggs and M. Wolff, Independence and Domination Separation in Chessboard Graphs, J. Combin. Math. Combin. Comput. 68 (2009), 3-17.

Cf. A002562, A129553.

A260189 a(n) = A033148(n) / 2^floor(n/4).

Original entry on oeis.org

1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 4, 8, 0, 0, 15, 22, 0, 0, 52, 51, 0, 0, 257, 342, 0, 0, 1589, 2609, 0, 0, 11417, 16896, 0, 0, 75375, 99114, 0, 0, 616010, 876579, 0, 0, 5253278, 8551800, 0, 0, 49667373, 79595269, 0, 0, 525731268, 764804085, 0, 0, 5932910966, 8905825760, 0, 0

Offset: 1

Vaclav Kotesovec, following a suggestion of Don Knuth, Jul 18 2015

W. Ahrens, Mathematische Unterhaltungen und Spiele, 2nd edition, volume 1, Teubner, 1910, pages 249-258.
Maurice Kraitchik, Le probleme des reines, Bruxelles: L'Échiquier, 1926, 18.

P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]

Cf. A002562, A032522, A033148, A037223, A037224.

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

A344227 Sprague-Grundy value for the Node-Kayles game played on the n-queens graph.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 1, 2, 3, 1, 0, 1, 0, 1

Offset: 0

Max Fan and Matthew K. Bardoe, May 13 2021

This game is also known as the Non-Attacking Queens game. Rules: two players successively place queens on an n X n chessboard such that the queens do not attack each other. The last player to place a queen wins.
Empirically, it appears that after the 9th term, the sequence oscillates between 1 and 0.
The n-queens graph considered here is not vertex-transitive. However, the toroidal version is and for Node-Kayles played on graphs that are vertex-transitive, it can be proven that the Sprague-Grundy value must be either 0 or 1.
Proof:
Each node in a graph that is transitive for all vertices has the same Sprague-Grundy value, since removing any node and its neighbors will produce identical graphs up to isomorphism.
This Sprague-Grundy value of the new graph must be either zero or nonzero.
If zero, then by the minimum exclusion principle, the value of the original graph is 1.
If nonzero, then by the minimum exclusion principle, the value of the original graph is 0.
Therefore, the Sprague-Grundy value of the original, vertex-transitive graph must be either 0 or 1.

G. Schrage, The eight queens problem as a strategy game, Int. J. Math. Educ. Sci. Technol. 17 (1989) 143-148. (mentions a restricted form of the Non-Attacking Queens game).

Matthew Bardoe, Non-Attacking Queens implementation in Python on Torus and non-Torus Chessboards.
Max Fan, Generalized Node-Kayles calculator implemented in Rust (terms 0 and terms 11-13 from Max Fan).
H. Noon, Surreal Numbers and the N-Queens Game, Bennington College, 2002 (includes this sequence).
H. Noon and G. Brummelen, The Non-Attacking Queens Game, The College Mathematics Journal., 224 (2006), 223-227 (Original problem description, terms 1-10 from H. Noon).

Cf. A000170, A002562, A036464, A316533, A316632, A316781, A002186.

pickCoords n = sequence (replicate 2 [0..n-1])
mex list = head (filter (`notElem` list) [0..(maximum list+1)])
checkIntersect [x,y] [n,m] = not (x == n || y == m) && (abs (x-n) /= abs (y-m))
nextMoves max history = filter (\move -> null history || all (checkIntersect move) history) (pickCoords max)
calcNimber max history | null (nextMoves max history) = 0 | otherwise = mex (map (\move -> calcNimber max (history ++ [move])) (nextMoves max history))
a344227 n = calcNimber n []

Rust
```
// See Fan link.
```

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

A103331 Number of ways to place n+1 queens and a pawn on an n X n board so that no two queens attack each other (symmetric solutions count only once).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A140450 The count of how many queens must be placed tentatively onto a board while seeking a first solution to the "N-Queens on an N x N chessboard" puzzle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A218244 Number of inequivalent (rotationally and reflectively distinct) ways to place n nonattacking empresses on n X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A062165 Number of ways of placing n nonattacking (normal) queens on n X n board, solutions similar on the torus count only once.

Views

Author

Keywords

Comments

Links

Extensions

A129552 Number of ways to place n+2 queens and 2 pawns on an n X n board so that no two queens attack each other (symmetric solutions count only once).

Views

Author

Keywords

Examples

Links

Crossrefs

A129554 Number of ways to place n+3 queens and 3 pawns on an n X n board so that no two queens attack each other (symmetric solutions count only once).

Views

Author

Keywords

Examples

Links

Crossrefs

A260189 a(n) = A033148(n) / 2^floor(n/4).

Views

Author

Keywords

References

Links

Crossrefs

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

PARI

A344227 Sprague-Grundy value for the Node-Kayles game played on the n-queens graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Rust

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

Views

Author

Keywords

Comments