How Many Latin Squares Are There? Counting Puzzle Grids

There are 12 Latin squares of order 3, 576 of order 4, and a 37-digit number of them, close to 9.98 × 10³⁶, of order 10 ^[1]. The exact order-10 count appeared in a paper published on 25 August 1995, and that paper could only estimate the counts for orders 11 to 15 ^[1].

So the honest answer to the question of how many Latin squares there are is: it depends on the size of the grid, and the numbers grow very fast. This article shows where these counts come from, why mathematicians first count a smaller set called normalized squares, how a computer handled the largest exact case, and how the same kind of counting question turns up when you ask how many loops can run through a grid.

What is a Latin square?

A Latin square of order n is a grid with n rows and n columns, filled with n different symbols so that no symbol appears twice in any row or in any column ^[1]. That single rule is the whole definition.

Here is one with four rows and four columns, written with the letters A, B, C and D.

Read any row or any column and you meet each letter exactly once. The same rule sits at the heart of number-place puzzles, which add an extra rule for small boxes, and of many grid puzzles where the task is to fill cells so that nothing repeats.

Every completed grid of that kind is a Latin square with extra conditions. So counting Latin squares tells you how much room puzzle makers have to work with before any other rule is added.

Why do mathematicians count normalized squares first?

Many Latin squares are simply rearrangements of each other. Swap two columns of a valid square and you get another valid square. Rename the symbols and you get yet another.

To avoid counting the same pattern over and over, mathematicians fix the edges. A Latin square is called normalized, or reduced, when its first row and its first column both list the symbols in their natural order ^[1]. The square above is normalized: its top row and its left column both read A, B, C, D.

The two counts are linked by a simple formula. For order n, the total number of Latin squares equals n! × (n − 1)! times the number of normalized ones ^[1]. Here n! means n multiplied by every whole number below it, down to one.

You can see why the formula works. Rearranging the columns of a normalized square in every possible order gives n! different first rows, and then rearranging every row below the top one multiplies that by the factorial of n minus one.

How does the count work for small grids?

Start with the smallest interesting case. Once the top row reads A, B, C and the left column reads A, B, C, there is only one way to finish, so there is exactly 1 normalized square of order 3 ^[1].

The reason is easy to check by hand. The second row starts with B, so its middle cell must be A or C. If it were A, the last cell would have to be C, but C already sits at the top of that column. So the second row is B, C, A, and the third row is forced to be C, A, B.

Multiplying by the formula gives 3! × 2! × 1 = 12 Latin squares of order 3 in total ^[1].

Order 4 has exactly 4 normalized squares ^[1]. Here they are, each starting with the row A, B, C, D, with the three lower rows shown.

The formula then gives 4! × 3! × 4 = 24 × 6 × 4 = 576 Latin squares of order 4 ^[1]. One size up, the same paper lists 56 normalized squares of order 5 ^[1].

How fast do the counts grow?

The table compares normalized squares with all Latin squares, order by order. The normalized counts are the ones listed in the 1995 paper, and the totals follow from its formula ^[1].

By our own arithmetic on the table, going from order four to order five multiplies the total by two hundred and eighty, while going from order nine to order ten multiplies it by more than a billion.

Each extra row and column multiplies the ways a grid can be completed, which is why the counts climb so steeply.

When was the order-10 count found?

The counts arrived slowly, one order at a time. According to the 1995 paper, the order-7 count was published in 1948, the order-8 count in 1967 and the order-9 count in 1975 ^[1].

The order-10 count was computed twice, independently, by the paper's two authors, in 1990 and 1991, using methods that were similar but not identical ^[1]. The paper reports the normalized count as 7,580,721,483,160,132,811,489,280 ^[1].

Each method took a few days on a fast workstation ^[1]. The paper reporting both results was published on 25 August 1995 ^[1].

How can a computer count numbers this large?

No computer can list that many squares one by one. The trick in the 1995 paper is to build a square row by row and to notice that many different partial squares behave in exactly the same way ^[1].

What matters is which symbols each column has already used. The paper records this as a pattern it calls a template, and many different partial squares share the same template ^[1]. The number of ways to finish a partial square depends only on the template, so it is worked out once for each kind of template and then reused ^[1].

Even so, the numbers of templates were large. With 5 rows placed in an order-10 square, there were 601,055 different templates under the first method's rules and 304,496 under the second, which also allowed the roles of columns and symbols to be swapped ^[1].

The general lesson is that symmetry is the main tool in counting puzzle grids. Whenever two partial grids are really the same up to renaming or reordering, a careful count handles them only once.

What about grids larger than order 10?

One size up, the same method breaks down. For order 11 with 5 rows placed, there were already 156,473,848 different templates under the weaker of the two definitions, far too many to finish in a reasonable time ^[1].

Instead, the 1995 paper estimated the larger counts ^[1]. The idea is to build a normalized square row by row, choosing each new row at random from all the rows that still fit, and to multiply together the number of choices available at each step ^[1]. Averaged over many trials, that product gives an unbiased estimate of the true count ^[1].

The authors could not state the accuracy precisely, but they judged that these estimates are probably correct to within one unit of the last digit shown ^[1]. Remember that these are normalized counts: the total number of Latin squares of each order is far larger still.

How do you count loops in a grid?

Latin squares are not the only grids worth counting. Loop puzzles ask you to draw one closed path through the dots of a grid, and a natural follow-up is how many such paths can exist.

Mathematicians study this on networks of points joined by lines, looking for closed tours that visit every point exactly once and end where they began ^[2]. Give every line a price and ask for the cheapest such tour, and you have the travelling salesman problem, a standard example of an NP-complete problem ^[2].

The counting result comes from a paper published on 21 June 2011, which looked at networks where each point meets exactly 3 lines ^[2]. Its algorithm writes out every closed tour of such a network, and the work it needs is bounded by a constant times 1.276ⁿ for n points ^[2]. The previous best bound was about 1.297ⁿ ^[2].

Since the algorithm produces every tour, the number of tours can never be larger than that same bound ^[2]. From below, some kinds of these networks are known to contain about 1.259ⁿ tours, so the true largest count sits in a narrow band between the two growth rates ^[2]. Whether the lower rate is exactly right was an open conjecture at the time ^[2].

By our own arithmetic, for a network of a hundred points the upper limit allows roughly thirty-eight billion tours, and the lower rate gives roughly ten billion. Networks in which points meet 3 lines only on average can contain even more, at least about 1.273ⁿ tours once n is large ^[2].

What simple rules does the counting method rely on?

The algorithm leans on a few plain facts about closed tours ^[2].

• A point that touches at most 1 line rules out any tour at all ^[2].
• If a run of points each touch exactly 2 lines, every tour has to use that whole run, so the run can be squeezed into a single line ^[2].
• Instead of changing the network as it goes, the method keeps one finished tour as a guide and moves along it point by point, and at many points it has just one option ^[2].

As our own observation, these rules resemble the forced moves people make in loop puzzles, such as a corner dot that leaves the path no choice. Dots inside a square grid usually touch more lines than the networks above, so the limits above do not carry over to grids directly.

How do the two counting problems compare?

Why should puzzle solvers care about these numbers?

Huge counts explain why puzzle makers never run out of fresh grids. They also explain why a good grid puzzle needs well-chosen clues: the clues must cut an enormous space of possible grids down to a single answer.

No one can try every filling of a large grid, but forced moves, symmetry and dead ends shrink the search. That is how mathematicians managed to count what they could not list.

How can you try this yourself?

• Write out the single normalized square with three rows, then rearrange its columns and lower rows in every way you can. You should reach 12 different Latin squares and no more ^[1].
• Start an order-4 square with the top row and left column fixed, and try to find all 4 normalized squares before looking at the table above ^[1].
• Draw a small grid of dots and look for every closed path that passes through each dot once. Notice how the corners force your first lines.

Counting is a puzzle skill in its own right. The riddle below asks you to count carefully without missing or repeating anything.