Torus Queen Independence

Abstract

Define a queen on ${\mathbb{Z}}_n^d$ with admissible moves parallel to $\mathbf{x}\in \{-1,0,1{\}}^d$, of arbitrary length. How many queens can be placed on ${\mathbb{Z}}_n^d$ without any two in conflict? In two dimensions, this problem was initiated by Pólya in 1918 and resolved by Monsky in 1989. We give the first known impossibility result in $d>2$ dimensions, showing that a trivial upper bound $n^{d-1}$ cannot be achieved if $n$ is a multiple of $5$ and not of $25$. Moreover, we conjecture that $n^{d-1}-O(n^{d-2})$ queens can be placed independently, which we prove if $n$ has no prime divisor less than $2^{\lfloor d/2\rfloor +1}$.