11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does the sentence "$(2,1)$ and $(1,2)$ form the first diagonal" mean? $\endgroup$ – 5xum Jun 12 '17 at 12:51
  • $\begingroup$ @5xum I mean position second cell in first column or first cell in second column, like in matrix. $\endgroup$ – kingW3 Jun 12 '17 at 12:55
  • 1
    $\begingroup$ This seems to by highly related to the 8 queens problem, if you think of all ones as queens, they may not be in the same row, column or diagonal. The same holds for all twos and so on. $\endgroup$ – mlk Jun 12 '17 at 13:00
  • $\begingroup$ I played with this once. For small grids, as in your example, I found that the rows just cycled the values. However, at 12x12, I found some solutions that did not do this. $\endgroup$ – badjohn Jun 12 '17 at 13:01
  • 1
    $\begingroup$ I found an old Java program that I wrote for this puzzle. It just uses brute force and ignorance. Assume that row 1 is 1, 2, 3, etc. Sizes 1, 2, 3, 4, 6, 8 have no solution. 5, 7, have a unique solution. This might suggest that there are no solutions for the even cases but there are multiple solutions for the 12 case. I am running the 9, 10, and 11 cases but, as you may expect, the program gets slower for these larger values. $\endgroup$ – badjohn Jun 12 '17 at 15:12
2
$\begingroup$

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:

enter image description here

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!

$\endgroup$
  • $\begingroup$ Thanks for the update. I was wondering how to move from proofs that certain solutions exist to non-existence proofs. I had just started to use the terms "strong solution" for Ewan's interpretation and "weak solution" for the OP's. $\endgroup$ – badjohn Jun 16 '17 at 16:45
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your $12\times 12$ example is wrong : for example, the $(11,1)$ and $(9,11)$ entries are both equal to $2$, yet they are on the same diagonal. $\endgroup$ – Ewan Delanoy Jun 15 '17 at 11:47
  • $\begingroup$ @EwanDelanoy I see what you mean but we seem to have different notions of the diagonal. I guess that you are imagining that the two sides are implicitly connected and a diagonal can travel off one side and continue on the other. My diagonals were not doing that. This comment from the OP, "(2,1) and (1,2) form the first diagonal" suggested my interpretation. $\endgroup$ – badjohn Jun 15 '17 at 11:57
  • $\begingroup$ The OP has been quiet for a while. We need him to say whether my example qualifies. Nonetheless, I will consider this interpretation as well. $\endgroup$ – badjohn Jun 15 '17 at 12:06
  • $\begingroup$ I too see what you mean. I think the OP should clarify this point. Personally if the sides are not implicitly connected I find the problem has less symmetry and beauty $\endgroup$ – Ewan Delanoy Jun 15 '17 at 12:08
  • $\begingroup$ @EwanDelanoy I like your interpretation and I will be trying it. I guess that you are connecting the top and bottom as well so, topologically, you are working with a torus. $\endgroup$ – badjohn Jun 15 '17 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.