

A344227


SpragueGrundy value for the NodeKayles game played on the nqueens 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 NonAttacking 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 nqueens graph considered here is not vertextransitive. However, the toroidal version is and for NodeKayles played on graphs that are vertextransitive, it can be proven that the SpragueGrundy value must be either 0 or 1.
Proof:
Each node in a graph that is transitive for all vertices has the same SpragueGrundy value, since removing any node and its neighbors will produce identical graphs up to isomorphism.
This SpragueGrundy 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 SpragueGrundy value of the original, vertextransitive 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) 143148. (mentions a restricted form of the NonAttacking Queens game).


LINKS

Table of n, a(n) for n=0..13.
Matthew Bardoe, NonAttacking Queens implementation in Python on Torus and nonTorus Chessboards.
Max Fan, Generalized NodeKayles calculator implemented in Rust (terms 0 and terms 1113 from Max Fan).
Vaclav Kotesovec, Nonattacking chess pieces, 6ed, 2013 (does not mention the Nonattacking chess pieces impartial game).
H. Noon, Surreal Numbers and the NQueens Game, Bennington College, 2002 (includes this sequence).
H. Noon and G. Brummelen, The NonAttacking Queens Game, The College Mathematics Journal., 224 (2006), 223227 (Original problem description, terms 110 from H. Noon).


PROG

(Rust) // See Fan link.
(Haskell)
pickCoords n = sequence (replicate 2 [0..n1])
mex list = head (filter (`notElem` list) [0..(maximum list+1)])
checkIntersect [x, y] [n, m] = not (x == n  y == m) && (abs (xn) /= abs (ym))
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



