17
$\begingroup$

Are there two orthogonal complete Latin squares of any order greater than 1? If so, what is the smallest order for which they exist?

(A Latin square of order $n$ is an $n\times n$ array of symbols $\{ s_1\ldots s_n \}$ such that each of the symbols appears exactly once in each row and in each column. Two Latin squares $L_{ij}$ and $G_{ij}$ are orthogonal if each of the $n^2$ pairs $(L_{ij}, G_{ij})$ is distinct; such a pair together form a Graeco-Latin square. A Latin square $L_{ij}$ is complete if each of the $n\cdot(n-1)$ pairs $(L_{ij}, L_{i+1,j})$ is distinct and if each of the $n\cdot(n-1)$ pairs $(L_{ij}, L_{i,j+1})$ is distinct.)

  • 0
    The very handsome equipment of [the game of *Qwirkle*](https://www.google.com/search?q=qwirkle&tbm=isch) consists of a set of 108 tiles, three depicting each of the 36 combinations of six shapes in six colors. I wanted to arrange 36 tiles in a $6\times 6$ array so to form a complete Graeco-Latin square. When I wasn't able to do so, I asked about it here, and learned that the task is impossible.2014-10-21
  • 0
    I would like to recommend an article, titled "Tuscan Squares" in The CRC Handbook of Combinatorial Designs, CRC Press, 2006, for more general situations than complete latin squares.2016-03-04

3 Answers 3

45

The problem is open no longer. It turns out that there are many pairs of orthogonal complete Latin squares of order 12. Here is one example. I also know how to build some bigger ones.

\begin{pmatrix} 1 & 2 & 5 & 7 & 4 & 8 & 9 &11 & 6 &12 &10 & 3\\ 7 &12 & 9 & 3 &10 & 2 & 1 & 5 & 8 & 4 & 6 &11\\ 2 & 3 & 6 & 8 & 5 & 9 &10 &12 & 1 & 7 &11 & 4\\ 8 & 7 &10 & 4 &11 & 3 & 2 & 6 & 9 & 5 & 1 &12\\ 10 & 9 &12 & 6 & 7 & 5 & 4 & 2 &11 & 1 & 3 & 8\\ 3 & 4 & 1 & 9 & 6 &10 &11 & 7 & 2 & 8 &12 & 5\\ 9 & 8 &11 & 5 &12 & 4 & 3 & 1 &10 & 6 & 2 & 7\\ 12 &11 & 8 & 2 & 9 & 1 & 6 & 4 & 7 & 3 & 5 &10\\ 11 &10 & 7 & 1 & 8 & 6 & 5 & 3 &12 & 2 & 4 & 9\\ 6 & 1 & 4 &12 & 3 & 7 & 8 &10 & 5 &11 & 9 & 2\\ 4 & 5 & 2 &10 & 1 &11 &12 & 8 & 3 & 9 & 7 & 6\\ 5 & 6 & 3 &11 & 2 &12 & 7 & 9 & 4 &10 & 8 & 1 \end{pmatrix}

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10 &11 &12\\ 6 & 4 &11 & 2 & 8 & 1 & 9 & 5 & 7 &12 & 3 &10\\ 4 &10 & 7 & 1 &11 & 9 & 3 &12 & 6 & 2 & 5 & 8\\ 9 & 1 & 5 &10 &12 & 4 & 6 &11 & 3 & 8 & 7 & 2\\ 2 &12 & 9 & 6 & 3 & 7 &11 &10 & 1 & 4 & 8 & 5\\ 3 & 9 &12 & 8 & 2 &10 & 4 & 7 & 5 &11 & 6 & 1\\ 10 & 8 & 6 & 9 & 7 & 3 & 5 & 2 & 4 & 1 &12 &11\\ 5 & 3 & 2 &11 & 1 & 8 &10 & 6 &12 & 7 & 4 & 9\\ 11 & 7 &10 & 5 & 4 &12 & 2 & 9 & 8 & 3 & 1 & 6\\ 8 &11 & 4 & 3 & 6 & 5 &12 & 1 &10 & 9 & 2 & 7\\ 7 & 6 & 8 &12 &10 & 2 & 1 & 3 &11 & 5 & 9 & 4\\ 12 & 5 & 1 & 7 & 9 &11 & 8 & 4 & 2 & 6 &10 & 3 \end{pmatrix}

  • 4
    Fantastic answer.2012-05-18
  • 3
    Thank you, and congratulations!2012-05-18
8

Further to what Doug wrote above, I can confirm that there is no pair of orthogonal complete latin squares of order 10 or less. There are 26088 normalized complete latin squares of order 10 (the next number for Doug's table). Of these only 64 possess an orthogonal mate, and none of those mates are themselves complete latin squares. You can download data on all these squares from my homepage at:

http://users.monash.edu.au/~iwanless/data/RCLS/index.html

  • 0
    This is a wonderful resource. Thanks very much.2012-05-08
  • 0
    Welcome to math.stackexchange.com!2012-05-08
5

As far as I know, this is still an open problem. It was posed by Keedwell in "Some problems concerning complete Latin squares" (1974).

Observation: If L and M are orthogonal complete Latin squares, then we can permute the symbols in L (or M) without affecting the orthogonality property, nor the completeness property. Hence, we can assume that the first row of L and M are in order (i.e. "normalised"). I wrote some code to check up to $8 \times 8$ squares, and found: \[ \begin{array}{|r|rrrrrrrr|} \hline n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\\ \text{nr. normalised complete Latin squares} & 1 & 0 & 2 & 0 & 8 & 0 & 192 & 0 \\\\ \hline \end{array} \]

None of the Latin squares encountered were orthogonal.

My guess is they exist, as there doesn't seem to be any reason for them not to exist. I suspect they don't exist for small orders simply because there's too many conditions placed on them.

Here's my C code below:

#include   /* change this to the order of your latin square */ #define ORDER_LATIN_SQUARE 9 #define MAX_NR_LATIN_SQUARES 100000  int n; int latin[ORDER_LATIN_SQUARE][ORDER_LATIN_SQUARE]; int latin2[ORDER_LATIN_SQUARE][ORDER_LATIN_SQUARE]; int complete_latin_squares[MAX_NR_LATIN_SQUARES][ORDER_LATIN_SQUARE][ORDER_LATIN_SQUARE]; int nr_complete_latin_squares=0; int nr_orthogonal_pairs_of_complete_latin_squares=0;  void print_latin_square() {   for(int i=0;i0 && i==1 && j==0) { printf("%f percent complete.\n",(float) (s-1)/(n-2)*100); }      for(int c=0;c0) {       int t=latin[i][j-1];       for(int r=0;r0) {       int t=latin[i-1][j];       for(int r=0;r

Here's a GAP version of the same program (it's slower, but it's nice to check the results are correct):

SetOfCompleteLatinSquares:=[];  GenerateCompleteLatinSquaresBacktrackingAlgorithm:=function(L,i,j,n)   local s,k,S1,S2,try_symbol;    # S1 is the set of extant pairs (l[r][c],l[r][c+1])    S1:=List([1..i-1],r->List([1..n-1],c->[L[r][c],L[r][c+1]]));   S1:=Concatenation(S1);   S1:=Concatenation([S1,List([1..j-2],c->[L[i][c],L[i][c+1]])]);    # S2 is the set of extant pairs (l[r+1][c],l[r][c])    S2:=List([2..i-1],r->List([1..n],c->[L[r-1][c],L[r][c]]));   S2:=Concatenation(S2);   if(i>1) then S2:=Concatenation([S2,List([1..j-1],c->[L[i-1][c],L[i][c]])]); fi;    for s in [1..n] do     try_symbol:=true;     for k in [1..j-1] do if s=L[i][k] then try_symbol:=false; fi; od; # row clash     for k in [1..i-1] do if s=L[k][j] then try_symbol:=false; fi; od; # column clash     if(j>1) then if([L[i][j-1],s] in S1) then try_symbol:=false; fi; fi; # row pair clash     if(i>1) then if([L[i-1][j],s] in S2) then try_symbol:=false; fi; fi; # column pair clash      if(try_symbol) then       L[i][j]:=s;       if(i=n and j=n) then         # Print(L,"\n");         Append(SetOfCompleteLatinSquares,[Immutable(L)]);       elif(j=n) then         GenerateCompleteLatinSquaresBacktrackingAlgorithm(L,i+1,1,n);       else         GenerateCompleteLatinSquaresBacktrackingAlgorithm(L,i,j+1,n);       fi;       L[i][j]:=0;     fi;   od; end;;  GenerateCompleteLatinSquares:=function(n)   local L,j;   L:=List([1..n],i->List([1..n],j->0));   for j in [1..n] do L[1][j]:=j; od; # assumes the first row is 1,2,..,n    SetOfCompleteLatinSquares:=[];   GenerateCompleteLatinSquaresBacktrackingAlgorithm(L,2,1,n);   return SetOfCompleteLatinSquares; end;; 
  • 0
    Thanks for this wonderful answer, particularly for the Keedwell reference.. I will wait 24 hours to make sure nobody else response and then accept it.2012-03-18
  • 0
    No worries, it's an interesting question. Note: there was a typo in the table, which I fixed.2012-03-18
  • 0
    Funny thing: I just happened to download a copy of the *Computational Problems in Abstract Algebra* anthology of 1970, edited by John leech, and when I opened it at random the first thing I saw was a paper by Keedwell about Latin squares. As far as I know I had never heard of him before your answer, and now he's popped up twice in a week.2012-03-18
  • 0
    The code just finished the n=9 case (it took about 2 days on my home computer).2012-03-20