How many Latin Squares?

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:

[[1, 2, 3],
 [3, 1, 2],
 [2, 3, 1]]

Another is:

[[3, 1, 2],
 [2, 3, 1],
 [1, 2, 3]]

Given an integer input n where n > 0, determine how many Latin Squares there are with a size n × n, where the possible values are anything from 1 to n inclusive.

Examples:

1 -> 1
2 -> 2
3 -> 12
4 -> 576
5 -> 161280
6 -> 812851200
7 -> 61479419904000
11 -> 776966836171770144107444346734230682311065600000 

This is OEIS sequence A002860. It has a Wikipedia article here.

Answers are only required to support inputs up to 6, due to anything above that being greater than 2³². However, while this is not strictly enforceable, your algorithm must work for all inputs.

Answer 1

Wolfram Language (Mathematica), 67 56 50 48 bytes

D[Permanent@a^n,##]&@@Join@@(a=x~Array~{n=#,#})&

Try it online!

Uses Theorem 5.1 in this article: if X is an n by n matrix whose entries are distinct variables, then the number of n by n Latin squares is equal to the coefficient of the product of all these variables in per(X)ⁿ, where per(X) is the permanent of X. Here, we obtain that coefficient by differentiating with respect to all of the variables, once each (which leaves a constant).

Regarding running time: TIO was happy to deal with inputs 1 through 6, and my laptop can handle 7 in a bit over 6 minutes. I didn't try 8.

Choice quotations included in the article about this formula's practicality:

The use of MacMahon's result by mere mortals seems doomed. – Riordan

One should not wish to actually perform, even in a computer algebra package like Maple, MacMahon's counting method. – Van Leijenhorst

Another Mathematica solution, 52 bytes

LineGraph@CompleteGraph@{#,#}~ChromaticPolynomial~#&

Much less efficient (only inputs 1 through 4 are viable) but somewhat more readable.

Uses the fact that Latin squares of size n are precisely the n-colorings of the n by n rook's graph, which is the line graph of the complete bipartite graph K_n,n, and is an excellent example of Mathematica's occasional tendency to look like a natural-language explanation of the algorithm with prepositions replaced by random symbols.

In practice, GraphData@{"Rook",{#,#}}~ChromaticPolynomial~#& is only 47 bytes and works for all feasible inputs, but it fails to satisfy the criterion of being a general algorithm (since GraphData hardcodes small rook graphs, but does not generate arbitrarily large ones).

Answer 2

Jelly, 8 bytes

Œ!ṗµfZ€L

Brute force solution. Inputs 5 and higher will time out on TIO.

Try it online!

How it works

Œ!ṗµfZ€L  Main link. Argument: n

Œ!        Generate all permutations of R := [1, ..., n].
  ṗ       Take the n-th Cartesian power, yielding the array A of all n×n matrices
          whose rows are permutations of R.
   µ      New chain. Argument: A
     Z€   Zip each; transpose each matrix in A, yielding the array B of all n×n
          matrices whose columns are permutations of R.
    f     Filter; keep only matrices that appear in A and B.
       L  Compute the length, counting the kept matrices.

Answer 3

Pyth, 11 bytes

l@K^.pQQCMK

Try it here!

How it works

l@K^.pQQCMK   - Full program.

    .pQ       - All permutations of the range [0, input).
   ^   Q      - To the Cartesian power of the input.
  K           - Assign to a variable K.
 @            - The intersection of K.
        CMK   - With the list of all elements in K transposed.
l             - Length.

As this is brute force, anything higher than 4 will Memory Error on Herokuapp or time out on TiO.

Answer 4

Python 2, 91 bytes

f=lambda n,k=0,s={''},x=0:k<n*n>x and f(n,k+1,s|{x+k/n,~x-k%n})+f(n,k,s,x+n)or len(s)>n*n*2

Try it online!

---

Python 2, 102 bytes

lambda n:sum(all(len({(k/r%n,i/n**k%n)for k in range(n*n)})/n/n for r in(1,n))for i in range(n**n**2))

Try it online!

Answer 5

Python 2, 138 134 124 bytes

from itertools import*
def f(n):r=range(n);print sum(map(set,zip(*m))==n*[set(r)]for m in product(permutations(r),repeat=n))

Try it online!

Brute forces, very slow. Works for n=1..4 on tio

Answer 6

Mathematica, 102 bytes

Length@Select[Subsets[Permutations@Range@#,{s=#}],Union[Sort/@Table[#[[i]]&/@#,{i,s}]]=={Range@s}&]s!&

Try it online!

Answer 7

Ruby, 90 bytes

Brute force!

->n{x=[*1..n]
y=*x.permutation
y.product(*[y]*~-n).count{|a|a.transpose.all?{|b|x-b==[]}}}

Try it online!