Matrix-pair permutation puzzle

matricespermutationspuzzle

Here's a puzzle. We have an $N \times N$ table. Inside each cell we write two numbers, $A_{ij}$ and $B_{ij}$, where $i,j$ denote row and column index. All numbers $A$ and $B$ are integers, $A,B \in [1, N]$. The constraints are as follows

  1. For each row $i$, all numbers $A_{ij}$ are different
  2. For each row $i$, all numbers $B_{ij}$ are different
  3. For each column $j$, all numbers $A_{ij}$ are different
  4. For each column $j$, all numbers $B_{ij}$ are different
  5. There are no two cells, for which the pair $(A,B)$ would be the same

Example solution for $N=3$

$$
\begin{pmatrix}
1,1 & 2,2 & 3,3 \\
2,3 & 3,1 & 1,2 \\
3,2 & 1,3 & 2,1
\end{pmatrix}
$$

Question: Determine for which $N$ there exists a solution. For those $N$ for which the solution exists, propose an algorithm to find 1 viable solution.

Best Answer

This is known as a Graeco-Latin Square. The only values for $N$ that do not have a solution are 2 and 6. Here is the wikipedia article for it:

Graeco-Latin Squares

There is also a proof for the non-existence of a solution for $N=6$ here:

Proof of non-existence for the $N=6$ case

Related Question