The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A344227 Sprague-Grundy value for the Node-Kayles game played on the n-queens graph. 1
 0, 1, 1, 2, 1, 3, 1, 2, 3, 1, 0, 1, 0, 1 (list; graph; refs; listen; history; text; internal format)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 25 18:33 EDT 2023. Contains 361528 sequences. (Running on oeis4.)