A sudoku-like grid with pairs of numbers

Question

It's easy to generate a 12x12 grid such that:

1. Each row contains the numbers 1 - 12
2. Each column contains the numbers 1 - 12
3. No row or column contains the same number twice

I am trying to determine if it's possible to generate a 12x12 grid where each cell contains two numbers -- A RED number between 1 and 12 and a BLUE number between 1 and 12 -- for which the following is true:

1. If you consider ONLY the RED numbers, the grid satisfies the three conditions above
2. If you consider ONLY the BLUE numbers, the grid satisfies the three conditions above
3. Every one of the 144 blue-red combinations is present in the grid.

I am pretty certain it's possible because I can do it with 3x3 and 4x4. Here is the 4x4, for example:

How can I generate the 12x12 grid?

UPDATE:

Arthur's answer below gave me enough info to create one. I am curious about an algorithm though. I'm guessing there is one based on the fact that this problem appears to fall into a documented category of problems (thanks Lord Shark the Unknown for point it out!!): https://en.wikipedia.org/wiki/Graeco-Latin_square

If anybody finds an algorithm I would love to see it.

Answer 1

Take your $4\times 4$ solution, then do it once more for 5-8, and once more for 9-12. Put them on top of one another. You now have a $12\times 4$ that is the start of a $12\times12$.

A $12\times12$ has $3\times 3$ blocks of size $4\times 4$. We have filled in the first three blocks. Call the pattern in the first block (your example) $\color{red}{A}\color{blue}{A}$, where the red $\color{red}{A}$ represents the pattern of the red numbers, and the blue $\color{blue}{A}$ represents the pattern of the blue numbers in that block. Similarly, call the other blocks $\color{red}{B}\color{blue}{B}$ and $\color{red}{C}\color{blue}{C}$.

Now fill in the rest of the large $3\times 3$ with your $3\times3$ solution on $A,B,C$, and then fill in for each $A,B,C$ the corresponding $4\times4$ pattern of coloured numbers. (If your $3\times 3$ solution doesn't start with the column $\color{red}{1}\color{blue}{1}, \color{red}{2}\color{blue}{2},\color{red}{3}\color{blue}{3}$, feel free to rearrange my block naming correspondingly.)

Answer 2

I just want to add to Arthur's solution by providing all possible Graeco-Latin squares of size 3 and 4 (up to reenumeration inside red or blue values or swapping red and blue) and one 12×12 which is a tensor product of first two squares.

Aa Bb Cc 
Bc Ca Ab 
Cb Ac Ba


Aa Bb Cc Dd 
Bc Ad Da Cb 
Cd Dc Ab Ba 
Db Ca Bd Ac 

Aa Bb Cc Dd 
Bc Ad Da Cb 
Db Ca Bd Ac 
Cd Dc Ab Ba 

Aa Bb Cc Dd 
Bd Ac Db Ca 
Dc Cd Ba Ab 
Cb Da Ad Bc 

Aa Bb Cc Dd 
Bd Ac Db Ca 
Cb Da Ad Bc 
Dc Cd Ba Ab 

Aa Bb Cc Dd 
Cd Dc Ab Ba 
Bc Ad Da Cb 
Db Ca Bd Ac 

Aa Bb Cc Dd 
Cd Dc Ab Ba 
Db Ca Bd Ac 
Bc Ad Da Cb

Aa Bb Cc Dd Ee Ff Gg Hh Ii Jj Kk Ll 
Bc Ad Da Cb Fg Eh He Gf Jk Il Li Kj 
Cd Dc Ab Ba Gh Hg Ef Fe Kl Lk Ij Ji 
Db Ca Bd Ac Hf Ge Fh Eg Lj Ki Jl Ik 
Ei Fj Gk Hl Ia Jb Kc Ld Ae Bf Cg Dh 
Fk El Hi Gj Jc Id La Kb Bg Ah De Cf 
Gl Hk Ej Fi Kd Lc Ib Ja Ch Dg Af Be 
Hj Gi Fl Ek Lb Ka Jd Ic Df Ce Bh Ag 
Ie Jf Kg Lh Ai Bj Ck Dl Ea Fb Gc Hd 
Jg Ih Le Kf Bk Al Di Cj Fc Ed Ha Gb 
Kh Lg If Je Cl Dk Aj Bi Gd Hc Eb Fa 
Lf Ke Jh Ig Dj Ci Bl Ak Hb Ga Fd Ec

Answer 3

There's a finite field construction which gives...

Theorem: For any prime power $q$, there exists a set of $q-1$ mutually orthogonal Latin squares.

This construction can be found via Google; e.g. some random mathematician's notes. If you don't like these notes, then search for something like orthogonal latin squares finite field MOLS.

Next taking direct products of orthogonal Latin squares give orthogonal Latin squares. Thus, there are straightforward constructions for all orders which are not of the form $2n$ for odd $n$.

Beyond this it gets hard. In fact, they don't even exist when $n \in \{1,3\}$. It's why Euler misconjectured that they don't exist in general. In the 1960s, Bose, Shrikhande, and Parker found that orthogonal Latin squares indeed exist except for orders $2$ and $6$.

This website claims there's a short proof by Zhu Lie in

Z. Lie, "A Short Disproof of Euler's Conjecture Concerning Orthogonal Latin Squares", Ars Combinatoria, 14(1982), pp. 47-55.

But I cannot readily confirm: Ars Combinatoria (table of contents) is not an easily accessible journal.