Proving a solution for the $n$-Queens Puzzle

Question

Given an $n$ x $n$ board, assume that $n \geq 5$ and that $n$ is not divisible by $2$ or $3$. Prove that the following positioning of $n$ queens $Q_0, Q_2, ..., Q_{n-1}$ works, i.e no two queens threaten each other:

For $0 \leq i \leq n-1$ we position the queen $Q_i$ on the field $(i, 2i \text{ } \pmod n)$.

Here we're using the ($x$-coordinate, $y$-coordinate) coordinate system, where $x$ describes the horizontal position, and $y$ the vertical. For example, in the formula above, $x$ would be $i$, and $y$ would be $2i \pmod n$.

My idea was to prove by contradiction and break up each case on how the queens are positioned to not threaten each other (horizontally, vertically and diagonally), but I can't see what follows. Can someone offer their thoughts or point me in the right direction?

Answer 1

Vertically: if $Q_i$ and $Q_j$ have the same $x$-coordinate, $i = j$ so they're the same queen.

Horizontally: if $Q_i$ and $Q_j$ have the same $y$-coordinate, $2i = 2j \pmod n$, so $2i = 2j + kn$ for some $k \in \mathbb{Z}$; since $n$ isn't divisible by 2, $k$ must be, and we have $i = j + (2k')n$, so $i = j \pmod n$. Since both $i$ and $j$ are $\le n$, they're equal.

Diagonally: we have two cases: the diagonals parallel to $(0, 0) \to (1, 1)$ and the 'antidiagonals'. First case: if $i - 2i = j - 2j \pmod n$, $-i = -j \pmod n$, so $i = j \pmod n$. Second case: if $i + 2i = j + 2j \pmod n$, so $3i = 3j + kn$ for some $k \in \mathbb{Z}$; since $n$ isn't divisible by 3, $k$ must be, and we have $i = j + (3k')n$, so $i = j \pmod n$.

Answer 2

Consider $i < j$ between 0 and $ n-1$. Of course, the first coordinate can’t be same for any two queens, hence they aren’t in same row.

Now, suppose, for the sake of contradiction, they lie on the same column. Then, $2(i-j) = nk$ for some natural $k$. Now, as n doesn’t contain 2 as it’s divisor, $k$ must be even. So, either $k$ is 0, which is not possible because that will contradict our assumption that $i$ and $j$ are not equal, or $k\geq 2$. In the latter case, $LHS = 2(i-j) < 2(n-1) < 2n \leq nk$, and hence $LHS \ne RHS$. Hence, we conclude that our assumption must have been incorrect and two queens positioned in this manner can’t lie on same column.

You still need to figure out the diagonal case.

Answer 3

For the diagonal case, split to two proofs - one for each "rotation" of the diagonal line.

When the diagonal line is "from top left to bottom right", then assume for the sake of contradiction we have two queens $i,j$. Then in order for them to be on the same diagonal line, there must be some $k$ where $i+k=j$ and $2i \pmod n + k =2j \pmod n$. Thus both $k=j-i$ and $k=2(j-i) \pmod n$.

Therefore, there must be some whole number $d$ with $k=2(j-i)+dn$. Substitute $k=j-i$ and get $i-j=dn$ and therefore $i-j = 0 \pmod n$. but both $0\le i,j\le n-1$ so we must have $i=j$ and therefore we have a contradiction.

The other "rotation" of the diagonal line uses the same idea.