I was messing around with a mostly-unrelated crypto problem, and I encountered this puzzle:
Let's define a "double Latin square":
1) It uses two-digit numbers, that start with 1-n, and also have a second digit in the range 1-n. (For example: 11, 12, 13, 21, 22, 23, 31, 32, 33)
2) Each number is used once
3) Each row and column has only one of each digit in both the most- and least- significant place. (So, 11 and 12 can't share a row/column, and neither can 11 and 21)
I wrote a solver to find solutions for me, and I've found solutions for 3x3, 4x4, and 5x5, but I can't find any for 6x6 or above.
Do any solutions exist?
Samples:
33 21 12
11 32 23
22 13 31
12 21 44 33
41 32 13 24
23 14 31 42
34 43 22 11
55 22 44 13 31
33 54 15 21 42
24 11 32 45 53
41 35 23 52 14
12 43 51 34 25
What you have essentially defined are othogonal Latins squares or Graeco-Latin squares (see here, e.g.). It states there that they exist for all $n \ge 3$ except $n=6$.
The fact that none exists for $n=6$ is called the $36$ officers problem.