1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ There are 576 4 x 4 latin squares. But the number grows rapidly. The number of 11 x 11 latin squares is said to be 776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000. The Wikipedia article is a useful introduction en.wikipedia.org/wiki/Latin_square $\endgroup$ – almagest May 5 '16 at 20:01
  • $\begingroup$ @almagest is it hard to show for n=4 ? $\endgroup$ – Arman Malekzadeh May 5 '16 at 20:58
  • $\begingroup$ Do you want the number of all Latin squares, or the number of Latin squares upto symmetries ? $\endgroup$ – Peter May 5 '16 at 21:09
  • $\begingroup$ @Peter the answer of my question is 576 . But i don't want the number ! i want the way to count them ! $\endgroup$ – Arman Malekzadeh May 5 '16 at 21:10
  • 1
    $\begingroup$ @Peter I consider symmetries :) $\endgroup$ – Arman Malekzadeh May 5 '16 at 21:24
0
$\begingroup$

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]).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.