\myheading{Practical use of Latin squares}

\begin{framed}
\begin{quotation}
For example, it turns out that orthogonal latin squares are enormously
useful, particularly in the design of experiments. Already in 1788, Francois
Crette de Palluel used a 4x4 latin square to study what happens when sixteen
sheep - four each from four different breeds - were fed four different diets and
harvested at four different times. [Memoires d'Agriculture (Paris: Societe Royale
d'Agriculture, trimestre d'ete, 1788), 17-23.] The latin square allowed him to do
this with 16 sheep instead of 64; with a Greco-Latin square he could also have
varied another parameter by trying, say, four different quantities of food or four
different grazing paradigms.\\
But if we had focused our discussion on his approach to animal husbandry,
we might well have gotten bogged down in details about breeding, about root
vegetables versus grains and the costs of growing them, etc. Readers who aren't
farmers might therefore have decided to skip the whole topic, even though latin
square designs apply to a wide range of studies. (Think about testing five kinds
of pills, on patients in five stages of some disease, five age brackets, and five
weight groups.) Moreover, a concentration on experimental design could lead
readers to miss the fact that latin squares also have important applications to
coding and cryptography (see exercises 18-24).
\end{quotation}
\end{framed}
( \TAOCPCombSearching{}. )

Maybe you got a program you want to test against different compilers, different optimization options, etc.
Maybe this program is CPU intensive app, like Bitcoin miner, SETI@home client or whatever.
And you're unsure, which compiler would produce the best code.

Say, you have 4 compilers, 4 optimization options and 4 computers to test everything.
Full test will take one day.
You can arrange all this like:

\begin{center}
\begin{tabular}{| l | l | l | l | l |}
\hline 
 Day    & Computer 1    & Computer 2    & Computer 3    & Computer 4 \\
        & Compiler 1    & Compiler 2    & Compiler 3    & Compiler 4 \\
\hline 
 Day  1 & Opt.options 1 & Opt.options 2 & Opt.options 3 & Opt.options 4 \\
\hline 
 Day  2 & Opt.options 2 & Opt.options 3 & Opt.options 4 & Opt.options 1 \\
\hline 
 Day  3 & Opt.options 3 & Opt.options 4 & Opt.options 1 & Opt.options 2 \\
\hline 
 Day  4 & Opt.options 4 & Opt.options 1 & Opt.options 2 & Opt.options 3 \\
\hline 
\end{tabular}
\end{center}

After testing, you'll find a best pair of compiler and optimization options.

This is a Latin square. You saw it often in Sudoku form, which is also Latin square, but with additional constraints
(9 3*3 boxes).

Thanks to Latin square, you could test all pairs in 4 days using only 4 computers.
Even if you have no idea about Latin squares and will try to find this arrangement manually, you'll come with a solution
similar to that, because there is no smaller solution.

Now the problem is harder: you have 4 frameworks/libraries/APIs to test.
Finally, you want to find a best triple: compiler + optimization options + framework.

For the problem like that it would be hard to find a good arrangement manually.
I'm using my small utility to find two Latin squares, that are mutually orthogonal to each other:

\begin{lstlisting}
first:   | mate:
0 1 2 3  | 0 3 1 2
1 0 3 2  | 1 2 0 3
2 3 0 1  | 2 1 3 0
3 2 1 0  | 3 0 2 1

concatenated:
00 13 21 32
11 02 30 23
22 31 03 10
33 20 12 01
\end{lstlisting}

Each pair in the final 'concatenated' (or superimposed) table is unique.
Now add this 'concatenated' table to ours:

\begin{center}
\begin{tabular}{| l | l | l | l | l |}
\hline 
 Day   & Computer 1 & Computer 2 & Computer 3 & Computer 4 \\
       & Compiler 1 & Compiler 2 & Compiler 3 & Compiler 4 \\
\hline 
 Day 1 &        0+0 &        1+3 &        2+1 &        3+2 \\
\hline 
 Day 2 &        1+1 &        0+2 &        3+0 &        2+3 \\
\hline 
 Day 3 &        2+2 &        3+1 &        0+3 &        1+0 \\
\hline 
 Day 4 &        3+3 &        2+0 &        1+2 &        0+1 \\
\hline 
\end{tabular}
\end{center}

Each pair of digits would reflect optimization options + framework.
Thanks to MOLS (Mutually Orthogonal Latin Squares) you can test all triplets (compiler + optimization options + framework)
(again) in 4 days using 4 computers.

Now the next problem: you also have 4 different operating systems.
macOS, Windows, and maybe two flavours of Unix.
3 MOLS would help.

\begin{lstlisting}
first:   | mate 1:  | mate 2:
0 1 2 3  | 0 2 3 1  | 0 3 1 2
1 0 3 2  | 1 3 2 0  | 1 2 0 3
2 3 0 1  | 2 0 1 3  | 2 1 3 0
3 2 1 0  | 3 1 0 2  | 3 0 2 1

first+mate 1 | first+mate 2 | mate 1+mate 2
00 12 23 31  | 00 13 21 32  | 00 23 31 12
11 03 32 20  | 11 02 30 23  | 11 32 20 03
22 30 01 13  | 22 31 03 10  | 22 01 13 30
33 21 10 02  | 33 20 12 01  | 33 10 02 21

first+mate 1+mate2:
000 123 231 312
111 032 320 203
222 301 013 130
333 210 102 021
\end{lstlisting}

These are 3 Latin squares where any pair of these 3 squares are orthogonal to each other.
Hence, in the final table you see only unique triplets.
Let's add this to our table:

\begin{center}
\begin{tabular}{| l | l | l | l | l |}
\hline 
 Day   & Computer 1 & Computer 2 & Computer 3 & Computer 4 \\
       & Compiler 1 & Compiler 2 & Compiler 3 & Compiler 4 \\
\hline 
 Day 1 &      0+0+0 &      1+2+3 &      2+3+1 &      3+1+2 \\
\hline 
 Day 2 &      1+1+1 &      0+3+2 &      3+2+0 &      2+0+3 \\
\hline 
 Day 3 &      2+2+2 &      3+0+1 &      0+1+3 &      1+3+0 \\
\hline 
 Day 4 &      3+3+3 &      2+1+0 &      1+0+2 &      0+2+1 \\
\hline 
\end{tabular}
\end{center}

Each unique triplet is: optimization options + framework + OS.
Again you need only 4 days and 4 computers to test each pair of these parameters and pick the best set
of compiler + optimization options + framework + OS.

Unfortunately, MOLS generation has its limits too.
Only small squares of order less than 10 are easy to generate.
Generation of larger is a very hard problem.
Despite of that, small MOLS are very useful.