The $n$-Queens Problem with Diagonal Constraints

Abstract

For a solution $S$ of the $n$-queens problem, let $M(S)$ denote the maximum of the absolute values of the diagonal numbers of $S$, and let $m(S)$ denote the minimum of those absolute values. For $n\ge 4$, let $F(n)$ denote the minimum value of $M(S)$, and let $f(n)$ denote the maximum value of $m(S)$, as $S$ ranges over all solutions of the $n$-queens problem. Say that a solution $S$ is an $n$-\emph{champion} if $M(S)=F(n)$ and $m(S)=f(n)$.

Approximately linear bounds are given for $F(n)$ and $f(n)$, along with computational results and several constructions together providing evidence that the bounds are excellent. It is shown that, in the range $4\le n\le 24$, $n$-champions exist except for $n=11,16,21,22$.