Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently read that the Sudokus are just Latin Squares for $n = 9$. I know that proving the number of Latin Squares is considered difficult to generalize in terms of $n$. I would like to know if there is any method of proving the unique number of Sudokus taking a special case for $n = 9$.

The Wikipedia page on Latin Squares shows that for $n = 9 , number\ of\ possible\ Latin\ Squares = 5524751496156892842531225600$. I would like to know different possible methods used to arrive at the answer (e.g using Brute-force , or generating for the reduced Latin-Squares or any other combinatorial method).

PS: I have also read this question asked here and the paper referred by the answer. I am not able to understand why the method fails for $n>11$. Even the OEIS page does not have sequences for $n>11$

share|improve this question
add comment

1 Answer 1

Sudokus are a proper subset of the Latin squares of order $9$, as they have the added restriction of the $3 \times 3$ boxes. Thus, all sudokus are Latin squares, but not all Latin squares are sudokus. As with Latin squares, there is no computer-free proof that these numbers are correct. Typically, these are checked by performing independent computations (possibly by slightly different methods).

That being said, most of the searching can be eliminated by identifying symmetries. Both Latin squares, in general, and sudokus have "symmetries", which can be exploited to give a significant reduction in the search space. In a Latin square, for instance, we can permute the rows arbitrarily to give another Latin square (so it'd be a waste of time to count all of these separately). I'm not particularly familiar with the methods used in enumerating sudokus, but a website by Jarvis (and the linked papers) offers much detail into his enumeration method.

There are $R_9=377597570964258816$ reduced Latin squares of order 9. I don't think any computer ever has counted from 1 to $R_9$, let alone play around with Latin squares at each step. Thus, it's safe to say a brute force enumeration is completely out of the question.

To date, the easiest way to find $R_9$ is to use Sade's method which I mention in my answer to the linked question. Sade's method is the only feasible way for order $10$ or greater. Unfortunately, Sade's method was published only in a very obscure paper and is hard to obtain. But I describe it in great detail in my survey paper (here).

Roughly speaking, Sade's method saves an enormous amount of time by identifying Latin rectangles that have the same number of completions, and clumping them together. We then count the number of ways of extending each equivalence class by one row, then identify which of these extended Latin rectangles admit the same number of completions, and so on recursively.

(Note: In an earlier version of this post, I claimed it was the only way for $9 \times 9$ squares, but there is actually another way in this case.)

For $9 \times 9$ Latin squares, it's possible to iterate through representatives of the 19270853541 main classes of Latin squares on a computer, and at each step calculate the size of the autoparatopism group $\mathrm{Par}(L)$. The total number of $9 \times 9$ Latin squares is thus \[\sum_L \frac{6n!^3}{|\mathrm{Par}(L)|},\] where the sum is over the 19270853541 representatives. Generating these representatives can be done via the "canonical construction path" described in:

B. D. McKay, Isomorph-free exhaustive generation, J Algorithms, 26 (1998), 306-324.

See this paper for more details (including the relevant definitions: "main class" and "autoparatopism"):

B. D. McKay, A. Meynert, W. Myrvold, Small Latin squares, quasigroups, and loops. J. Combin. Des. 15 (2007), 98-119.

Sade's method for $12 \times 12$ Latin squares would work fine, if we had a sufficiently powerful computer with enough memory (and the budget to use it, and know-how to program it efficiently). I think it's safe to say we (as a species) could find this number in the next 100 years or so (I'm hoping to see $R_{12}$ before I die).

Note that the number of Latin squares grows quite fast. Most people think $n!$ grows quickly. Well, Smetaniuk showed that $L_{n+1} \geq (n+1)!\ L_n$ (where $L_n$ counts non-reduced Latin squares). The sheer number of Latin squares is the obstacle here.

B. Smetaniuk, A new construction of Latin squares. II. The number of Latin squares is strictly increasing, Ars Combin., 14 (1982), pp. 131-145.

share|improve this answer
    
$R_9 \approx 3e17$. That's no longer an "absurdly large" number for tasks that are parallelizable. The fastest supercomputer runs 20,000 Terraflops, ie $2e16$ floating point operations in one second. –  Nick Alger Oct 11 '12 at 11:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.