Max Fan - cp's OEIS frontend

User: Max Fan

Max Fan has authored 1 sequences.

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

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

cp's OEIS Frontend

User: Max Fan

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