\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
\frame{\includegraphics[scale=0.5]{\CURPATH/knuth_q.png}}
\caption{The problem}
\label{fig:knuth_MOLS3_10}
\end{figure}

\begin{figure}[H]
\centering
\frame{\includegraphics[scale=0.5]{\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}[basicstyle=\ttfamily\footnotesize,caption=Commands]
# 2 solutions
# Knuth_a="3145926870281976350494523071686208451793836409521759812740364627530981057614832917306894527093812645"
my_time.py ./MOLS2_par.py --solver gimsatul --all-solutions --normalize --first
3145926870281976350494523071686208451793836409521759812740364627530981057614832917306894527093812645

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

# 12,265,168 solutions
# Knuth_e="7823456019823406719523401789563401289567401239567856789123406789523401019563478219567408239567801234"
my_time.py ./MOLS2_par.py --solver gimsatul --all-solutions --normalize --first
7823456019823406719523401789563401289567401239567856789123406789523401019563478219567408239567801234
\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{framed}
\begin{quotation}
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{quotation}
\end{framed}
( \url{https://en.wikipedia.org/wiki/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
2718459036028713564975240931681435962780639071842540692718533102684597987154630289563072145643820971
\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
1680397425834651209798057613422754689130053897621449638205717192034658621940578334712589065027143869
\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:\\
\url{https://math.stackexchange.com/questions/649548/find-three-10-times10-orthogonal-latin-squares}.

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
3145926870281976350494523071686208451793836409521759812740364627530981057614832917306894527093812645
\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{}