# How many Latin Squares?

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 232. However, while this is not strictly enforceable, your algorithm must work for all inputs.

• – Okx
Nov 2, 2017 at 15:05
• Are you sure counting Latin squares is NP complete? Can you please give a reference?
– xnor
Nov 2, 2017 at 15:07
• @xnor Actually, I'm not sure that this problem specifically is NP complete, but I know something else related to Latin Squares is. As I don't have any proof for this problem specifically, I've removed it.
– Okx
Nov 2, 2017 at 15:09
• Maybe you're thinking of completing a partially filled Latin square?
– xnor
Nov 2, 2017 at 15:09
• @xnor Yes, that's it.
– Okx
Nov 2, 2017 at 15:10

# Wolfram Language (Mathematica), 675650 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)n, 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.

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

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


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

• You can shave two bytes by avoiding K: l@FCMB^.p Nov 2, 2017 at 23:34

# 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!

# Python 2, 138134 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

# Mathematica, 102 bytes

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


# 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!