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

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

Offset

0,4

Comments

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.

References

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).

Links

Table of n, a(n) for n=0..13.

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).

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013 (does not mention the Non-attacking chess pieces impartial game).

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).

Prog

(Rust) // See Fan link.
(Haskell)
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 []

Crossrefs

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

Sequence in context: A205379 A238881 A070094 * A325521 A275875 A105497

Adjacent sequences: A344224 A344225 A344226 * A344228 A344229 A344230

Keyword

more,nonn

Author

Max Fan and Matthew K. Bardoe, May 13 2021

Status

approved