\myheading{Mutually orthogonal Latin squares: naive idea}

\ac{AKA} Graeco-Latin squares.

\renewcommand{\CURPATH}{latin/MOLS_naive}

\leveldown{}

\myheading{The principle}

First I created a function that multiply two one-hot values.
Which seemed to be very simple.
To multiply $x$ and $y$, create square where each variable would be True if both variables
from $x$ and $y$ would be True at this intersection.

\begin{lstlisting}[style=custompy]
def mult_one_hots(self, x:List[int], y:List[int]) -> List[int]:
    assert len(x)==len(y)
    in_size=len(x)
    z=[]
    for i in range(in_size):
        for j in range(in_size):
            z.append(self.AND(x[i], y[j]))
    assert len(z)==in_size**2
    return z
\end{lstlisting}
( The full file: \url{\RepoURL/libs/SAT_lib.py} )

Using this function, I can join two \ac{LS} into \ac{MOLS}:

\begin{lstlisting}[style=custompy]
def make_mutually_orthogonal(SIZE, s, a, b):
    t=[]
    for r in range(SIZE):
        for c in range(SIZE):
            t.append(s.mult_one_hots(a[r][c], b[r][c]))

    for x in my_utils.transpose_matrix(t):
        s.OR_always(x)
\end{lstlisting}
( The full file: \url{\RepoURL/latin/latin_utils.py} )

Each pair must be present in the final solution, hence you see OR\_always() at the end.

The full source code: \url{\RepoURL/\CURPATH/MOLS2_par.py}.

In reasonable time, it can find:
2-MOLS(7): \url{\RepoURL/\CURPATH/2-MOLS7.txt};
2-MOLS(8): \url{\RepoURL/\CURPATH/2-MOLS8.txt};
2-MOLS(9): \url{\RepoURL/\CURPATH/2-MOLS9.txt};
2-MOLS(10): \url{\RepoURL/\CURPATH/2-MOLS10.txt}.
Using Gimsatul (10 threads) on AMD Ryzen 5 3600 6-Core Processor.

\myheading{Donald Knuth's exercise}

We will try to solve this problem from \TAOCPCombSearching{}:

\begin{figure}[H]
\centering
\myfbox{\includegraphics[width=1\textwidth]{\CURPATH/knuth_q.png}}
\caption{The problem}
\label{fig:knuth_MOLS3_10}
\end{figure}

\begin{figure}[H]
\centering
\myfbox{\includegraphics[width=1\textwidth]{\CURPATH/knuth_a.png}}
\caption{The solution}
\end{figure}

I'm fixing solution's column to be in ascending order (0,1,2,3...) like in D.Knuth's solutions:
solutions count would be multiple of $10!$ otherwise (number of isomorphic squares).

\begin{lstlisting}[caption=Commands]
# 2 solutions
# Knuth_a="314...645"
my_time.py ./MOLS2_par.py --solver gimsatul \
        --all-solutions --normalize --first 314...645

# 6 solutions
# Knuth_c="057...740"
my_time.py ./MOLS2_par.py --solver gimsatul \
        --all-solutions --normalize --first 057...740

# 12,265,168 solutions
# Knuth_e="782...234"
my_time.py ./MOLS2_par.py --solver gimsatul \
        --all-solutions --normalize --first 782...234
\end{lstlisting}

2 solutions for (a): \url{\RepoURL/\CURPATH/TAOCP_a.txt}

6 solutions for (c): \url{\RepoURL/\CURPATH/TAOCP_c.txt}

Some solutions for (e) (not all): \url{\RepoURL/\CURPATH/TAOCP_e.txt}

All timings: Gimsatul using 10 threads running on AMD Ryzen 5 3600 6-Core Processor.

\myheading{Proofs}

\emph{Thirty-six officers problem} is a well-known classic problem. Citing Wikipedia:

\begin{my_quote}
A problem similar to the card problem above was circulating in St. Petersburg in the late 1700s and, according to folklore, Catherine the Great asked Euler to solve it, since he was residing at her court at the time.[7] This problem is known as the thirty-six officers problem,[8] and Euler introduced it as follows:[9][10]

A very curious question, which has exercised for some time the ingenuity of many people, has involved me in the following studies, which seem to open a new field of analysis, in particular the study of combinations. The question revolves around arranging 36 officers to be drawn from 6 different regiments so that they are ranged in a square so that in each line (both horizontal and vertical) there are 6 officers of different ranks and different regiments.
— Leonhard Euler
\end{my_quote}
( \href{https://en.wikipedia.org/wiki/Mutually\_orthogonal\_Latin\_squares}{wikipedia: Mutually orthogonal Latin squares} )

It was proved by Gaston Tarry in 1901.
But we can prove it as well.

In other words, we will try to find a 2-MOLS(6), but this is impossible, my script would report UNSAT.
But can we create a proof?

\begin{lstlisting}
my_time.py ./MOLS2_par.py --solver gimsatul \
        --normalize --proof --size 6
\end{lstlisting}

The proof file size: $\approx 31$ MiB.

However, when I tried to find a proof for non-normalized \ac{LS}, things are bad.
Gimsatul was running for more than 14 hours and it produced already $\approx 200$ GiB proof,
so I had to interrupt it.

Presumably, the problem in much larger search space.
There are just 9,408 reduced L(6) (\ac{OEIS}: A000315), but 812,851,200 non-reduced L(6) (\ac{OEIS}: A002860).

It's also possible to find proofs for two L(10) from \ac{TAOCP} that has no \ac{MOLS}:

\begin{lstlisting}[basicstyle=\ttfamily\footnotesize]
# Knuth_b
my_time.py ./MOLS2_par.py --solver gimsatul \
        --all-solutions --normalize --proof --first 271...971
\end{lstlisting}

$\approx 5$ minutes using Gimsatul on 10 cores.
The proof size: $\approx 600$ MiB.

\begin{lstlisting}[basicstyle=\ttfamily\footnotesize]
# Knuth_d
my_time.py ./MOLS2_par.py --solver gimsatul \
        --all-solutions --normalize --proof --first 168...869
\end{lstlisting}

$\approx 5$ minutes using Gimsatul on 10 cores.
The proof size: $\approx 600$ MiB.

\myheading{Finding 3-\ac{MOLS}}

Almost the same, but 3 \ac{LS}, all 3 pairs are orthogonal to each other.
\url{\RepoURL/\CURPATH/MOLS3_par.py}.

In reasonable time, it can find:
3-MOLS(7): \url{\RepoURL/\CURPATH/3-MOLS7.txt};
3-MOLS(8): \url{\RepoURL/\CURPATH/3-MOLS8.txt}.
Using Gimsatul (10 threads) on AMD Ryzen 5 3600 6-Core Processor.

Of course, finding 3-MOLS(10) is not (yet?) possible.

Finding 3 Latin squares of order 10 is a problem marked as having maximal (50) difficulty in \ac{TAOCP}.
[See the problem 15: \ref{fig:knuth_MOLS3_10}.]
A discussion on the Stack Exchange:\\
\href{https://math.stackexchange.com/questions/649548/find-three-10-times10-orthogonal-latin-squares}{URL}.

3-MOLS(9) is also out of reach.

However, we can prove that there is no 3-MOLS(10) for specific \ac{LS}.
Let's take L(10) (a) from \ac{TAOCP}, for which 2 \ac{MOLS} exists.

\begin{lstlisting}[basicstyle=\ttfamily\footnotesize]
my_time.py ./MOLS3_par.py --solver gimsatul \
        --all-solutions --normalize --proof --first 314...645
\end{lstlisting}

The proof file is $\approx 1$ GiB.

I tried to do the same for L(10) (e) \ac{LS}, but that is out of reach, because (e) \ac{LS} has 12,265,168 \ac{MOLS} and
search space is much larger.

Of course, checking all L(10) (even narrowed to reduced/normalized, isotopy/main classes) is not possible
\footnote{At \ac{OEIS}, see: A002860, A000315, A040082, A003090.}.
There are 34,817,397,894,749,939 main classes for L(10).

\levelup{}

