cp's OEIS Frontend

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

%I A344227 #54 May 27 2025 06:24:57
%S A344227 0,1,1,2,1,3,1,2,3,1,0,1,0,1
%N A344227 Sprague-Grundy value for the Node-Kayles game played on the n-queens graph.
%C A344227 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.
%C A344227 Empirically, it appears that after the 9th term, the sequence oscillates between 1 and 0.
%C A344227 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.
%C A344227 Proof:
%C A344227 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.
%C A344227 This Sprague-Grundy value of the new graph must be either zero or nonzero.
%C A344227 If zero, then by the minimum exclusion principle, the value of the original graph is 1.
%C A344227 If nonzero, then by the minimum exclusion principle, the value of the original graph is 0.
%C A344227 Therefore, the Sprague-Grundy value of the original, vertex-transitive graph must be either 0 or 1.
%D A344227 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).
%H A344227 Matthew Bardoe, <a href="https://github.com/mbardoe/NonAttackingQueens">Non-Attacking Queens implementation in Python on Torus and non-Torus Chessboards</a>.
%H A344227 Max Fan, <a href="https://github.com/InnovativeInventor/node-kayles">Generalized Node-Kayles calculator implemented in Rust</a> (terms 0 and terms 11-13 from Max Fan).
%H A344227 H. Noon, <a href="http://web.archive.org/web/20210127044904/https://liacs.leidenuniv.nl/~kosterswa/nqueens/papers/noon2002.pdf">Surreal Numbers and the N-Queens Game</a>, Bennington College, 2002 (includes this sequence).
%H A344227 H. Noon and G. Brummelen, <a href="https://web.archive.org/web/20230306021157/https://www.maa.org/sites/default/files/may_2006_-_noon55524.pdf">The Non-Attacking Queens Game</a>, The College Mathematics Journal., 224 (2006), 223-227 (Original problem description, terms 1-10 from H. Noon).
%o A344227 (Rust) // See Fan link.
%o A344227 (Haskell)
%o A344227 pickCoords n = sequence (replicate 2 [0..n-1])
%o A344227 mex list = head (filter (`notElem` list) [0..(maximum list+1)])
%o A344227 checkIntersect [x,y] [n,m] = not (x == n || y == m) && (abs (x-n) /= abs (y-m))
%o A344227 nextMoves max history = filter (\move -> null history || all (checkIntersect move) history) (pickCoords max)
%o A344227 calcNimber max history | null (nextMoves max history) = 0 | otherwise = mex (map (\move -> calcNimber max (history ++ [move])) (nextMoves max history))
%o A344227 a344227 n = calcNimber n []
%Y A344227 Cf. A000170, A002562, A036464, A316533, A316632, A316781, A002186.
%K A344227 more,nonn
%O A344227 0,4
%A A344227 _Max Fan_ and Matthew K. Bardoe, May 13 2021