Finding all Latin Squares of order 5

Question

A Latin Square is a square of size n × n containing numbers 1 to n inclusive. Each number occurs once in each row and column.
An example of a 3 × 3 Latin Square is:
$$
left(
begin{array}{ccc}
 1 & 2 & 3 
 3 & 1 & 2 
 2 & 3 & 1 
end{array}
right)
$$
Another is:
$$
left(
begin{array}{ccc}
 3 & 1 & 2 
 2 & 3 & 1 
 1 & 2 & 3 
end{array}
right)
$$
My code can work when the order is less than 5
n=4;
Dimensions[ans=Permutations[Permutations[Range[n]],{n}]// 
  Select[AllTrue[Join[#,Transpose@#],DuplicateFreeQ]&]]//AbsoluteTiming

{0.947582, {576, 4, 4}}

When the order is 5, the memory is not enough, I want to know if there is a better way to get all 5×5 Latin squares?

Roman · Accepted Answer

Adding lines one-by-one and continuing only if the newly added line does not give any column duplications. This highly unoptimized code takes about a minute for $n=5$ (thanks @chyanog for speedup!):
addline[lines_] := 
  Select[Append[lines, #] & /@ Permutations[Range[Length[Transpose[lines]]]],
         AllTrue[DuplicateFreeQ]@*Transpose]
latinsquares[n_] := Nest[Join @@ addline /@ # &,
                         Transpose[{Permutations[Range[n]]}],
                         n - 1]

latinsquares[5]
(*    {{{1,2,3,4,5},{2,1,4,5,3},{3,4,5,1,2},{4,5,2,3,1},{5,3,1,2,4}},
       {{1,2,3,4,5},{2,1,4,5,3},{3,4,5,1,2},{5,3,1,2,4},{4,5,2,3,1}},
       {{1,2,3,4,5},{2,1,4,5,3},{3,4,5,2,1},{4,5,1,3,2},{5,3,2,1,4}},
       ...
       {{5,4,3,2,1},{4,5,2,1,3},{3,2,1,5,4},{2,1,4,3,5},{1,3,5,4,2}}}    *)

flinty · Answer

If you do a "BacktrackSearch" then it will take forever for $n=5$ but use less memory. There are 161280 $5times5$ Latin squares - I recommend you test this with smaller numbers first like $n=3$:
latinQ[mtx_] := 
  AllTrue[mtx, DuplicateFreeQ] && 
   AllTrue[Transpose@mtx, DuplicateFreeQ];

n = 5;
lsquares = ResourceFunction["BacktrackSearch"][
   ConstantArray[Permutations[Range[n]], n],
   latinQ, latinQ, 161280
];

Neil Strickland · Answer

We can say that a latin square is standard if the first row is [1,...,n] and the first column is also [1,...,n].  Any latin square arises uniquely as follows: take a standard latin square, apply an arbitrary permutation to the full set of n columns, then apply an arbitrary permutation to the last (n-1) rows.  Thus, the number of standard squares is smaller than the full set of squares by a factor n! (n-1)!, which is 2880 in the case n=5.
It is most efficient to find the standard squares by search, and then just apply permutations to get the rest.
If you were using C you could encode everything using bit patterns and then it would only take a few processor cycles worth of bit operations to test the admissibility of each potential new row, which would be extremely fast.  I don't know how well you could do in Mathematica (I'm just a tourist on this particular stackexchange site.)

Finding all Latin Squares of order 5

3 Answers

Add your own answers!

Ask a Question