Are there complete Graeco-Latin squares?

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}

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

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 <stdio.h>

/* 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;i<n;i++) {
    for(int j=0;j<n;j++) {
      printf("%d ",latin[i][j]);
    }
    printf(" ");
  }
  printf("\n");
}

void print_latin_square2() {
  for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
      printf("%d ",latin2[i][j]);
    }
    printf(" ");
  }
  printf("\n");
}

int are_orthogonal_latin_squares() {
  for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
      for(int r=0;r<n;r++) {
        for(int c=0;c<n;c++) {
          if(!(i==r && j==c)) {
            if(latin[i][j]==latin[r][c] && latin2[i][j]==latin2[r][c]) { return 0; }//i,j,r,c
          }
        }
      }
    }
  }
  return 1;
}

/*
backtracking algorithm for generating complete latin squares
proceeds row-by-row, then column-by-column
never introduces one of the following clashes:
- two symbols in the same row
- two symbols in the same column
- two order pairs of symbols (l(i,j),l(i,j+1))=(l(r,c),l(r,c+1))
- two order pairs of symbols (l(i+1,j),l(i,j))=(l(r,c),l(r+1,c))
*/

void generate_complete_latin_squares_backtracking_algorithm(int i, int j) {
  for(int s=0;s<n;s++) {
    if(s>0 && i==1 && j==0) { printf("%f percent complete.\n",(float) (s-1)/(n-2)*100); }

    for(int c=0;c<j;c++) { if(latin[i][c]==s) { goto dont_use_this_symbol; } } /* s would occur twice in row i */
    for(int r=0;r<i;r++) { if(latin[r][j]==s) { goto dont_use_this_symbol; } } /* s would occur twice in column j */

    /* check for (latin[i][j-1],s) occuring already */
    if(j>0) {
      int t=latin[i][j-1];
      for(int r=0;r<i;r++) {
        for(int c=0;c<n-1;c++) {
          /* (latin[i][j-1],s) occurs as (latin[r][c],latin[r][c+1]) where r<i */
          if(latin[r][c]==t && latin[r][c+1]==s) { goto dont_use_this_symbol; }
        }
      }
      for(int c=0;c<j-1;c++) {
        /* (latin[i][j-1],s) occurs as (latin[r][c],latin[r][c+1]) where r=i and c<j-1 */
        if(latin[i][c]==t && latin[i][c+1]==s) { goto dont_use_this_symbol; }
      }
    }

    /* check for (latin[i-1][j],s) occuring already */
    if(i>0) {
      int t=latin[i-1][j];
      for(int r=0;r<i;r++) {
        for(int c=0;c<n;c++) {
          /* (latin[i-1][j],s) occurs as (latin[r][c],latin[r+1][c]) where r<i-1 */
          if(latin[r][c]==t && latin[r+1][c]==s) { goto dont_use_this_symbol; }
        }
      }
      for(int c=0;c<j-1;c++) {
        /* (latin[i-1][j],s) occurs as (latin[r][c],latin[r+1][c]) where r=i-1 and c<j */
        if(latin[i][c]==t && latin[i][c+1]==s) { goto dont_use_this_symbol; }
      }
    }

    /* trying symbol s for entry l[i][j] */
    latin[i][j]=s;
    if(i==n-1 && j==n-1) {
      for(int r=0;r<n;r++) { for(int c=0;c<n;c++) {
        complete_latin_squares[nr_complete_latin_squares][r][c]=latin[r][c];
      } }
      print_latin_square();

      /* checks if any of the earlier-discovered complete latin squares are othogonal */
      for(int t=0;t<nr_complete_latin_squares;t++) {
        for(int r=0;r<n;r++) { for(int c=0;c<n;c++) { latin2[r][c]=complete_latin_squares[t][r][c]; } }
        if(are_orthogonal_latin_squares()) {
          printf("Orthogonal complete Latin squares found!\n");
          print_latin_square();
          print_latin_square2();
          printf("\n");
          nr_orthogonal_pairs_of_complete_latin_squares++;
        }
      }
      nr_complete_latin_squares++;
      goto dont_use_this_symbol;
    }
    if(j==n-1) {
      generate_complete_latin_squares_backtracking_algorithm(i+1,0);
      goto dont_use_this_symbol;
    }
    generate_complete_latin_squares_backtracking_algorithm(i,j+1);

    dont_use_this_symbol: 
    latin[i][j]=-1;
  }
}

int main() {
  n=ORDER_LATIN_SQUARE;

  for(int j=0;j<n;j++) { latin[0][j]=j; } /* assumes the first row = 0,1,..,n */
  for(int i=1;i<n;i++) { for(int j=0;j<n;j++) { latin[i][j]=-1; } } /* -1 denotes an empty cell */
  generate_complete_latin_squares_backtracking_algorithm(1,0);

  printf("\nFound %d complete Latin squares of order %d.\n",nr_complete_latin_squares,n);
  printf("Found %d pairs of orthogonal complete Latin squares of order %d.\n",nr_orthogonal_pairs_of_complete_latin_squares,n);

  return 1;
}

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;;