Closing the gap and settling the problem of queens on an $n\times n$ board, each attacking at most one other

Abstract

Let $q(n)$ denote the largest number of queens that can be placed on an $n\times n$ chessboard so that no queen attacks more than one other queen. We prove that $q(n)=\lfloor 4n/3\rfloor$ for every $n⩾6$, and that $q(n)=n$ for $n⩽5$, which settles a previously conjectural value. As a corollary, we also settle that, in the version of the problem where each queen attacks \emph{exactly} one other queen, the answer is $2\lfloor 2n/3\rfloor$, again as previously conjectured.

10 pages, 5 figures