A319235
The profile of the backtrack tree for the eight queens problem.
Original entry on oeis.org
1, 8, 42, 140, 344, 568, 550, 312, 92
Offset: 0
- D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.
A319236
The profile of the backtrack tree for the sixteen queens problem.
Original entry on oeis.org
1, 16, 210, 2236, 19688, 141812, 838816, 3998456, 15324708, 46358876, 108478966, 193892860, 260303408, 253897632, 171158018, 72002088, 14772512
Offset: 0
- D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.
A319283
Number of nodes of the backtrack tree for the n queens problem.
Original entry on oeis.org
1, 2, 3, 6, 17, 54, 153, 552, 2057, 8394, 35539, 166926, 856189, 4674890, 27358553, 171129072, 1141190303, 8017021932, 59365844491, 461939618824
Offset: 0
- D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.
A319288
a(n) is the smallest k such that A319284(n, k) >= A319284(n, j) for all 0 <= j <= n.
Original entry on oeis.org
0, 0, 1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 11, 11, 12, 13, 14, 15
Offset: 0
A343905
Number of ways of placing n nonattacking range-3 leprechauns on an n X n board.
Original entry on oeis.org
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 34, 4, 112, 516, 7312, 81324, 1056560, 13443944, 171919446, 2195838076, 28876216900, 379982087060
Offset: 1
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
- 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).
-
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 []
-
// See Fan link.
A383738
Number of solutions to the n-queens puzzle in a n X n board that are not square root permutations of {n-1,...,2,1,0}.
Original entry on oeis.org
0, 0, 0, 0, 8, 4, 40, 92, 352, 724, 2680, 14192, 73704, 365596, 2279184, 14772448, 95814976, 666090624, 4968057848, 39029188404, 314666222008, 2691008701644, 24233937684440, 227514171970408, 2207893435805088, 22317699616364044, 234907967154122528
Offset: 1
For n = 5, we have:
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
0 | Q | | Q | | Q | | Q | | Q |
1 | Q | | Q | | Q | | Q | | Q |
2 | Q | | Q | | Q | | Q | | Q |
3 | Q | | Q | | Q | | Q Q | | Q |
4 | Q | | Q | | Q | | | | Q |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
0,2,4,1,3 0,3,1,4,2 1,3,0,2,4 1,4,2,0,3 2,0,3,1,4
is sqrt perm: no no no yes no
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
0 | Q | | Q | | Q | | Q | | Q |
1 | Q | | Q | | Q | | Q | | Q |
2 | Q | | Q | | Q | | Q | | Q |
3 | Q | | Q | | Q | | Q | | Q |
4 | Q | | Q | | Q | | Q | | Q |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
2,4,1,3,0 3,0,2,4,1 3,1,4,2,0 4,1,3,0,2 4,2,0,3,1
is sqrt perm: no yes no no no
In total there are 10 solutions for a 5 X 5 board with 5 queens, of which 8 are not square root permutations of {n-1,...,2,1,0}.
Then, a(5) = 10.
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
a(4)=16 because any queen attacks all but two other squares and every solution is counted twice by enumerating all such placements.
A168553
a(n) = 1 if it is possible to place n sets of n queens on an n X n chessboard with no two queens of the same set attacking each other.
Original entry on oeis.org
1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1
Offset: 1
For n=1 a single queen is a solution. For n=2 or 3 there is no single-set solution. For n=4, there are 2 single-set solutions, and they can both fit on the board together, but these are insufficient to make a 4-set solution. For n=5, there is a doubly-periodic single-set solution by Polya's construction, which can be tiled to make a 5-set solution
- G. Polya, Uber die 'doppelt-periodischen' Losungen des n-Damen-Problems. In Mathematische Unterhaltungen und Spiele, W. Ahrens, Ed., Teubner, Leipzig, 1918, pp. 364-374.
A000170 gives the number of single-set solutions.
A007705 gives the number of Polya-style doubly-periodic single-set solutions (with even n omitted since they are all 0).
A178986
Number of ways to place n nonattacking amazons (superqueens) on an n X n toroidal board.
Original entry on oeis.org
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 44, 0, 1092, 0, 0, 0, 16932, 0, 24776, 0, 0, 0, 1881492, 0
Offset: 1
Comments