When it comes down to it, there has only been one important step towards an "easy to compute" formula for $L_n$, the number of Latin squares of order $n$. This was by Sade:
A. A. Sade, Énumération des carrés latins, application au 7e ordre, conjecture pour les orders supérieurs, privately published, (1948). 8 pp.
Sade gave a method for non-constructive counting of Latin squares. More specifically, he clumped together Latin rectangles that have the same number of completions (as recognised by their "template"). Subsequent authors have merely implemented Sade's method on a computer...
For order 10:
B. D. McKay and E. Rogoyski, Latin squares of order ten, Electron. J. Combin.,
2 (1995). N3, 4 pp.
For order 11:
B. D. McKay and I. M. Wanless, On the number of Latin squares, Ann. Comb.,
9 (2005), pp. 335–344.
I discuss this in my survey paper and PhD thesis (both are open access).
I have often thought about performing the computation for $12 \times 12$ Latin squares, which would be a particularly ambitious project. The difference between $11 \times 11$ and $12 \times 12$ is huge. Here are some quotes which highlight the difficulty (here $R_n=n!(n-1)!L_n$):
McKay, Wanless (2005) write:
It is unlikely that $R_{12}$ will be computable by the same method for some time, since the number of regular bipartite graphs of order 24 and degree 6 is more than $10^{11}$.
Stones, Wanless (2012) (link) write:
McKay and Rogoyski and Kuznetsov gave $R_{12} \approx 1.62 \cdot 10^{44} > 3 \cdot 10^{10} \cdot R_{11}$... Barring the discovery of a faster algorithm, the evaluation of $R_{12}$ will remain infeasible for some years yet.
To me, it doesn't seem completely out-of-the-question to find $R_{12}$ within the next 30 or so years. It would require the use of some kind of supercomputer, and (presumably) a hybrid GPU-CPU implementation. However, the cost and effort required to do this would probably far exceed the benefit of finding $R_{12}$.
Estimates for the number of Latin squares of order $n$ are around, however, most recently by:
C. Zhang and J. Ma, Counting solutions for the N-queens and Latin square problems by Monte Carlo simulations, Phys. Rev. E, 79 (2009). 016703.
Other comments:
- There are several known bounds and congruences for $L_n$.
- There are many formulae for $L_n$ (which are impractical to use, but theoretically interesting).
- Counting $k \times n$ Latin rectangles, for fixed $k$, is theoretically "easy", since these number satisfy linear recurrences, as proved in:
I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc. 16 (1) (1987) 79–83.
(see also Doyle's formula, which is currently the best way to count $k \times n$ Latin rectangle for $n \leq 6$.)
- I don't think it's possible to give a proper answer to the question: why is it hard to count Latin squares? It might be easy, and we haven't been clever enough yet. But the general idea as to why I think it is hard, is that, when constructing Latin squares, early decisions can affect the number of completions (and thus need to be accounted for in an enumeration). Compare to row-Latin squares ($n \times n$ matrices in which each symbol appears in every row, and we allow duplicates in columns). The number here is $n!^n$. Here, early decisions don't affect the number of completions.
Best Answer
If $L_n$ is the number of Latin squares of order $n$, and $R_n$ is the number of reduced Latin squares of order $n$, then $$L_n = n!(n-1)! R_n.$$ The factor $n! (n-1)!$ comes about by counting:
Given any Latin square of order $n$, there is a unique permutation of the columns so that the first row is in order ($1,2,\ldots,n$), after which there is a unique permutation of the rows which fixes the first row so that the first column is in order.
In the other direction, given a reduced Latin square of order $n$, if we permute the rows except the first and permute the columns, we generate $n! (n-1)!$ distinct Latin squares of order $n$.
So, every reduced Latin square corresponds to $n! (n-1)!$ (not necessarily reduced) Latin squares, and every (not necessarily reduced) Latin square gives exactly one reduced Latin square.
As such, computing $L_n$ is effectively the same as computing $R_n$. While there are many formulae for the number of Latin squares, computationally they're only effective up to $n=11$. With the current best counting technique (Sade's method), as hardware improves, we might see $L_{12}$ in our lifetimes.
As far as I know, Sade's method is the only method which has been used for $n \geq 10$.
For orders $n \leq 9$, it is possible to generate main class representatives for each main class, computing their main class size using nauty, the sum of which equals $L_n$ (not an easy task for $n=9$ [I'm not sure if anyone has actually done it this way]; representatives can be downloaded on Brendan McKay's website for $n \leq 8$).
It possible to use Doyle's formula to compute the number of $6$-line Latin rectangles, which, for $7$ columns, is equal to $L_7$ (ref.).