0
$\begingroup$

In the $n$-queens problem, we attempt to place $n$ queens on an $n \times n$ chessboard so that no two of the queens attack each other; that is, no two queens share a row, column, or diagonal.

A modular solution to the $n$-queens problem satisfies a stricter condition. Here, the diagonals wrap around one side of the board to continue around the other side. We still do not want queens to share rows, columns, or diagonals, but now it is harder. Equivalently, a modular solution is a solution which continues to work after a (modular) translation of the board is applied (say, every queen shifts $i$ to the right and $j$ down, identifying the $1^{\text{st}}$ row as the one that comes next the last and likewise for column).

It was shown by Pólya that the $n$-queens problem can only have modular solutions if $\gcd(n,6) = 1$; equivalently, if $n \equiv \pm 1 \pmod 6$. (See section 5 of A survey of known results and research areas for $n$-queens by Bell and Stevens for more details.)

My question is: if $\gcd(n,6) = 1$, then are all solutions modular? Or can there be normal solutions which are not preserved by translation?

$\endgroup$
3
  • 2
    $\begingroup$ Please explain what you mean by a modular solution. $\endgroup$
    – saulspatz
    Apr 1, 2019 at 18:42
  • $\begingroup$ I mean solutions which remain solution after a (modular) translation of the board is applied (say, every queen shifts i to the right and j down, identifying the 1st row as the one that comes next the last and likewise for column) A modular solution has the property that even after a shift like that it remains a solution $\endgroup$
    – karlabos
    Apr 1, 2019 at 18:46
  • $\begingroup$ How can a gcd be negative? $\endgroup$
    – Servaes
    Apr 1, 2019 at 21:29

1 Answer 1

2
$\begingroup$

It seems that all $5$ queens solutions are modular, but here is a $7$ queens solution which is not: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline &Q\rule[-0.6ex]{0ex}{3ex}\\ \hline &&&Q\rule[-0.6ex]{0ex}{3ex}\\ \hline Q\rule[-0.6ex]{0ex}{3ex}\\ \hline &&&&&&Q\rule[-0.6ex]{0ex}{3ex}\\ \hline &&&&Q\rule[-0.6ex]{0ex}{3ex}\\ \hline &&Q\rule[-0.6ex]{0ex}{3ex}\\ \hline &&&&&Q\rule[-0.6ex]{0ex}{3ex}\\ \hline \end{array} $$ Rotating this board to the left or right will cause a conflict between the queens on the third and fourth rows.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .