How to count the latin squares of order 4

Question

a Latin square is an $n × n$ array filled with n different symbols, each occurring exactly once in each row and exactly once in each column.

So, Assume that an integer like $4$ is given. How many $4 × 4$ latin squares exist? Generally, What's the idea for counting them ?

Answer 1

For order 4, there's not many. We can just enumerate them using a backtracking algorithm (essentially a depth first search: we proceed cell-by-cell, filling it in in all possible non-clashing ways, then continuing to the next cell). Here's some GAP code I just whipped up:

# order of the Latin square
n:=4;;

# number of Latin squares found so far
count:=0;

# start with the empty Latin square
L:=List([1..n],i->List([1..n],j->0));;

# function for trying all non-clashing symbols in cell (i,j)
ExtendPartialLatinSquare:=function(i,j)
  local s;

  # try symbol s in cell (i,j)
  for s in [1..n] do

    # symbol s already used in column j
    if(ForAny([1..i-1],k->L[k][j]=s)) then continue; fi;

    # symbol s already used in row i
    if(ForAny([1..j-1],k->L[i][k]=s)) then continue; fi;

    # no clashes arise
    L[i][j]:=s;

    # if L is a Latin square, count it;
    # otherwise try filling in the next empty cell
    if(j=n) then
      if(i=n) then
        count:=count+1;
        Display(L);
      else
        ExtendPartialLatinSquare(i+1,1);
      fi;
    else
      ExtendPartialLatinSquare(i,j+1);
    fi;

    L[i][j]:=0;

  od;
end;;

ExtendPartialLatinSquare(1,1);

Print("Found ",count," Latin squares of order ",n,"\n");

which displays the 576 Latin squares of order 4. (It even works for the 161280 Latin squares of order 5.)

Enumeration in this way is not so easy for larger orders (Sade's algorithm is the only method that's been used for orders 8 or more, but it's non-constructive [as it must be--the numbers are simply too large]).