When is a Sudoku like table solvable

Question

Given a $n\times n$ table is it possible to fill each cell with one of the numbers $1,2,3,\cdots,n$ such that in each column,each row and each diagonal (i.e Denoting $(x,y)$ as number of column and row $(2,1)$ and $(1,2)$ form the first diagonal) every number appears exactly once? For which $n$ can we fill the table?

---

Context: I've been given this problem on a contest few months ago but just for $n=4,5$ which I solved easily since $n=4$ is impossible and for $n=5$ we have $$$$\begin{array}{|c|c|c|c|c|} \hline 1&2&3&4&5\\ \hline 3&4&5&1&2\\ \hline 5&1&2&3&4\\ \hline 2&3&4&5&1\\ \hline 4&5&1&2&3\\ \hline\end{array}$$$$ But I was interested in a more general statement I think I've also proved that for $n=6$ it's impossible by trying to fill the table manually. My guess is that for even $n$ it's not solvable and for odd $n$ it's solvable but I have no idea how to approach it except to fill it manually.

EDIT: For prime $n$ we can fill each cell $(i,j)$ with $i+2j\pmod{n}$ except when $i+2j\equiv0\pmod{n}$ then we write $n$ instead for example such filling with $n=7$ (the $n=5$ example is the same filling if you look at $(j,i)$ instead of $(i,j)$) $$$$\begin{array}{|c|c|c|c|c|c|c|} \hline 3&5&7&2&4&6&1\\ \hline 4&6&1&3&5&7&2\\ \hline 5&7&2&4&6&1&3\\ \hline 6&1&3&5&7&2&4\\ \hline 7&2&4&6&1&3&5\\\hline 1&3&5&7&2&4&6\\\hline2&4&6&1&3&5&7\\\hline\end{array}$$$$

PROOF OF THE EDIT: For the same row if cells $(i_1,j)$ and $(i_2,j)$ have the same value we have that $$i_1+2j\equiv i_2+2j\pmod{n}$$ implies $i_1\equiv i_2$ which is possible only if $i_1=i_2$. Same logic applies to the column for cells $(i,j_1),(i,j_2)$ we get $$i+2j_1\equiv i+2j_2\pmod{n}$$ when $n$ is prime it implies $j_1=j_2$ if $(i_1,j_1),(i_2,j_2)$ are on a diagonal we have $$|i_1-i_2|=|j_1-j_2|$$ now assuming they have the same value $$i_1+2j_1\equiv i_2+2j_2\pmod{n}$$ then $i_1-i_2\equiv 2(j_2-j_1)\pmod{n}$ which implies $1\equiv \pm 2\pmod{n}$ which is absurd.

Answer 1

This is not an answer but hopefully a contribution to an answer.

Double diagonal Latin squares or just diagonal Latin squares (the terminology seems to vary) are Latin squares where both main diagonals (sometimes called the main and the anti-main) also have the property that all $N$ symbols occur exactly once. I realize that your requirement is that all "minor" diagonals also don't have repeating symbols, but it should be clear that a necessary condition for this, is that the square must be a diagonal Latin square.

In this paper there is a proof on page $4$ which shows that, if there are numbers A and B from the range $[0, N-1]$ which satisfy the properties:

• A is relatively prime to N
• B is relatively prime to N
• (A + B) is relatively prime to N
• (A - B) is relatively prime to N

then you can generate a diagonal Latin square with the following rule:

Cell$(i,j) = (A * i + B * j) \mod N$

This is like the rule you found but without the strict requirement that $N$ is prime. A corollary to the above theorem is that if $N$ is an odd number not divisible by $3$, there is a diagonal Latin square of order $N$. So I tried the formula with the first odd non-prime fulfilling the corollary's requirement $(N=25)$ and got the following:

It seems to me this is a square of the type you are looking for, and with $N$ odd, but not a prime.

Edit

We can also show that with an even $N$, no diagonal Latin square can be generated using the method above. If $N$ is even, both $A$ and $B$ must be odd. But then both $(A+B)$ and $(A-B)$ must be even and can therefore not be relatively prime to $N$.

Edit 2

I made a program to generate diagonal Latin squares based on the formula above and then to check if all diagonals were without repeats. I ran the program for all odd $N$ between $3$ and $1001$ and the result is that all squares, where $N$ is not divisible by $3$, fulfilled the requirements! I therefore conjecture that the corollary above is not only true for diagonal Latin squares but also for "kingW3" squares.

Edit 3

Ladies and gentlemen, I have found a very nice document which answers many of our questions. In fact, if we use the definition of "diagonal" assumed by @Ewan Delanoy (called "broken diagonals" in the document), it basically solves the OP:

1. It proves the conjecture I made above
2. It proves that if the definition of "diagonal" is "broken diagonals", no solutions exist for even $N$
3. It gives an outline of a proof (leaving the details as homework!) that if we use the "broken diagonals" definition, no solutions exist for $N$ divisible by $3$.

Enjoy!

Answer 2

This is only a partial answer but it is too large to be a comment. I looked at this problem a long time ago and I wrote a Java program which tried to crack it by brute force and ignorance.

I only looked at cases in which the first row is the selected symbols in order. Any other solution is "isomorphic" to one of this form.

When the size is above 9, I use A, B, C, etc in a hexadecimal style.

For size 1, there is a trivial solution

$$ \begin{array} {|c|} \hline 1\\ \hline \end{array} $$

for sizes 2, 3, and 4, there is no solution.

Size 5 has a solution as posted by kingW3 in his original post. There is a second which is in a sense a reflection. Each row is offset by 3 to the right which can be viewed as 2 to the left hence the reflection comment.

Size 6 has no solution.

Size 7 has 4 solutions here is one which is similar to kingW3's solution for size 5. Each row is offset 2 to the right. The others are offset by 3, 4, and 5.

$$ \begin{array} {|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7\\ \hline 3&4&5&6&7&1&2\\ \hline 5&6&7&1&2&3&4\\ \hline 7&1&2&3&4&5&6\\ \hline 2&3&4&5&6&1&2\\ \hline 4&5&6&7&1&2&3\\ \hline 6&7&1&2&3&4&5\\ \hline \end{array} $$

Note the simple cyclic pattern shared by size 5.

Size 8 has no solution.

This hints at a pattern: even unsolvable, odd solvable with a cyclic pattern.

The pattern does not continue. At size 9, that cyclic style does not work. My cracking program just completed for size 9; there is no solution.

I won't run the cracking program on size 10. It would probably not finish before I die.

The cyclic patterns work for size 11. So, as kingW3 has found, a prime size helps which makes sense once you know.

However, this does not cover all solutions. Here is one for size 12. I have a memory, but no records, of others.

$$ \begin{array} {|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7&8&9&A&B&C\\ \hline 5&6&C&1&B&2&3&A&7&4&8&9\\ \hline 9&A&4&8&6&1&B&5&C&2&7&3\\ \hline B&7&9&3&A&C&8&1&4&6&5&2\\ \hline 8&C&5&2&7&4&9&6&A&1&3&B\\ \hline 3&B&7&6&C&A&5&4&2&8&9&1\\ \hline A&4&1&9&8&3&2&B&5&C&6&7\\ \hline C&8&2&5&1&B&6&9&3&7&A&4\\ \hline 4&1&6&A&3&8&C&7&B&9&2&5\\ \hline 6&3&B&C&9&7&4&2&8&5&1&A\\ \hline 2&9&8&7&4&5&A&3&1&B&C&6\\ \hline 7&5&A&B&2&9&1&C&6&3&4&8\\ \hline \end{array} $$

Additional case.

I have a solution for size 25. It is the cyclic style. I think that will work if the size is coprime to 2 and 3 but I have not proved that yet.

The 12 case remains interesting as it is not of the cyclic style.

Update

On further thought, I now believe for size $n$ and a shift per line of $s$, a cyclic solution exists provided that all of $s - 1$, $s$, and $s + 1$ have order $n$ in $\mathbb{Z}_n$ (as an additive group). In other words, they are all non-zero and either $1$ or coprime to $n$. This can be simplified to Jens's rule of odd and not divisible by $3$.

The $12\times12$ example above remains the only exceptional case that we know.