\myheading{Mutually orthogonal Latin squares: finding via transversals}
\label{MOLS_transv}

\renewcommand{\CURPATH}{latin/MOLS_transv}

\leveldown{}

This is the method mentioned in \TAOCPCombSearching{}.
Named by D.Knuth as Euler-Parker method.

First, find all transversals in \ac{LS}.
Transversal is a set of squares/symbols.
All symbols must be differrent in transversal.
All rows and columns must be also different.

These are first 3 transversals of L(10) (a) from \ac{TAOCP}:

\begin{figure}[H]
\centering
\frame{\includegraphics[scale=0.4]{\CURPATH/TAOCP_a_first_3_transv.png}}
%\caption{The solution}
\end{figure}

More transversals for that L(10): \url{https://www.youtube.com/watch?v=8pDCTNvgOmE}.

On average, L(10) has $\approx 800$ transversals.

Then find such a set of 10 transversals, so that L(10) will be covered and each square will be covered by one transversal.
This is no different from pentomino tiling problem \ref{tiling} and solved using exact cover problem.

For L(10) (a) from TAOCP there are two ways of covering (each transversal colored by each color):

\begin{figure}[H]
\centering
\frame{\includegraphics[scale=0.5]{\CURPATH/TAOCP_a_two_sets.png}}
%\caption{The solution}
\end{figure}

(L(10) (e) from TAOCP has 5504 transversals
\footnote{By the way, that square visualized as a cube: \url{https://www.youtube.com/watch?v=gnNq-J5kcl4}.
Clearly, you can see here some symmetries/regularities.}.
Here is also a video where these transversals are combined: \url{https://www.youtube.com/watch?v=ifvKt_ts8DE}.)

Then add the following constraint: second square (or mate): each transversal in mate must have same number/symbol.

This divides the task to 3 subtasks:
1) find all transversals in \ac{LS} (fast);
2) combine $order$ transversals using exact cover problem (toughest step);
3) find mate for transversals set ($order!$ permutations).

That method was used in 1959 by E.T.Parker.
Citing Wikipedia:

\begin{framed}
\begin{quotation}
Then E. T. Parker found a counterexample of order 10 using a one-hour computer search on a UNIVAC 1206 Military Computer while working at the UNIVAC division of Remington Rand (this was one of the earliest combinatorics problems solved on a digital computer).
\end{quotation}
\end{framed}
( \url{https://en.wikipedia.org/wiki/Mutually\_orthogonal\_Latin\_squares} )

The famous magazine cover:

\begin{figure}[H]
\centering
\frame{\includegraphics[scale=0.5]{\CURPATH/1959.jpg}}
\caption{Scientific American, November 1959}
\end{figure}
( See also: \url{http://www.martin-gardner.org/SciAm12.html}. )

Of course, this method is way more faster than my first \emph{naive} idea.
But more sophisticated.

Here I found mates for TAOCP squares.
(a): \url{\RepoURL/\CURPATH/TAOCP_a.txt};
(c): \url{\RepoURL/\CURPATH/TAOCP_c.txt};
some mates for (e): \url{\RepoURL/\CURPATH/TAOCP_e.txt}.

The source code: \url{\RepoURL/\CURPATH/MOLS.py}.
Some transversals code is in: \url{\RepoURL/latin/latin_utils.py}.

Using this method I can find 2-MOLS(11): \url{\RepoURL/\CURPATH/2-MOLS11.txt},
2-MOLS(12): \url{\RepoURL/\CURPATH/2-MOLS12.txt},
2-MOLS(13): \url{\RepoURL/\CURPATH/2-MOLS13.txt}.
(All timings are for AMD Ryzen 5 3600.)

I had no success in finding 2-MOLS(14), for days.

The proofs of \ac{MOLS} absence are possible as well:

\begin{lstlisting}[basicstyle=\ttfamily\footnotesize]
# no solutions
# Knuth_b="2718459036028713564975240931681435962780639071842540692718533102684597987154630289563072145643820971"
my_time.py ./MOLS.py --proof --first
2718459036028713564975240931681435962780639071842540692718533102684597987154630289563072145643820971
\end{lstlisting}

The proof file filesize: $\approx 47$MiB.

\begin{lstlisting}[basicstyle=\ttfamily\footnotesize]
# no solutions
# Knuth_d="1680397425834651209798057613422754689130053897621449638205717192034658621940578334712589065027143869"
my_time.py ./MOLS.py --proof --first
1680397425834651209798057613422754689130053897621449638205717192034658621940578334712589065027143869
\end{lstlisting}

The proof file filesize: $\approx 49$MiB.

But this proof is different from proofs generated by my \emph{naive} version.
These are proofs of inexistance of solutions for exact cover problem.
Which are, of course, the same as proofs of inexistance of mates for these \ac{LS}.

\myhrule{}

However, finding 3-MOLS(n) using this method is not as good as my \emph{naive} method, described previously.
The \emph{naive} method can find 3-MOLS(8) easily, but this method is not competitive.

Probably because the \emph{naive} method find triple \emph{in parallel}.

While this method do this sequentially: it finds a first \ac{LS},
then tries to find a \ac{LS} that is \ac{MOLS} for the first \ac{LS},
then tries to find a third \ac{LS} which is \ac{MOLS} for first and second \ac{LS}.
That is 3 stages.

\levelup{}