3
$\begingroup$

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?

$\endgroup$
3
5
$\begingroup$

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}}}    *)
$\endgroup$
1
  • 1
    $\begingroup$ AllTrue[Transpose[#], DuplicateFreeQ]& is a little faster than And @@ DuplicateFreeQ /@ Transpose[#] &. $\endgroup$
    – chyanog
    May 16 at 16:51
4
$\begingroup$

If you do a "BacktrackSearch" then it will take forever for $n=5$ but use less memory. There are 161280 $5\times5$ 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
];
$\endgroup$
1
  • $\begingroup$ This can do 5000 n=5 squares per 15 seconds on my machine. It probably gets harder to find the last few solutions that haven't already been encountered, as it will spend more time checking its memory, so expect it to take much longer than 10 minutes. $\endgroup$
    – flinty
    May 16 at 15:10
1
$\begingroup$

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

$\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.