The Number of Possible Sudoku Puzzles

Date: 03/04/2006 at 14:14:55
From: Neville
Subject: The Number of Possible Sudoku Puzzles

As you know, Sudoku is a current craze, although its best days may 
have already passed.  I assume you are familiar with the game.

I have been thinking about how many possible variations there are.  
By my reckoning the number is factorial nine times six to the sixth 
power, i.e., 16,930,529,280.

My decision to write to you was triggered by a recent newspaper 
article on Benjamin Franklin’s Squares giving the number of possible 
solutions to Franklin's puzzle as about one million plus.  The article 
also states that there are about 6 sextillion Sudoku solutions, where 
a sextillion is either 10 to the 21(American) or 10 to the 36 
(British).  Either way the number is much larger than mine.

My reasoning goes as follows:

1) Given a properly completed solution another can be generated by a 
one-to-one mapping of the numbers 1 to 9, e.g.,

Original:	1 2 3 4 5 6 7 8 9
Mapped:    	2 8 7 3 9 1 4 6 5
 
2) There are 9! such mappings, producing a Basic Set [Defined Term] of 
362,880 solutions.

3) Within each solution in the Basic Set it is possible to permute the 
rows and columns of each minor (3x3) square.  For example, rows 1,2 
and 3 can be permuted six ways, as can columns 1,2 and 3. Similarly, 
the other two sets of rows and the other two sets of columns can be 
commuted in the same way.

These permutations can be combined in 6 to the power 6, i.e., 46,656 
ways.  I believe, but cannot prove, that any such combination will 
not match any other such combination or any member of the Basic Set.

4) Hence I reckon there 362,880 x 46,656, i.e., 16,930,529,280 unique 
Sudoku puzzles.

Neville

Date: 03/05/2006 at 17:16:59
From: Doctor Vogler
Subject: Re: The Number of Possible Sudoku Puzzles

Hi Neville,

Thanks for writing to Dr. Math.  Let's look at your work:

>1) Given a properly completed solution another can be generated by a 
>one-to-one mapping of the numbers 1 to 9, e.g.,
>
>Original: 1 2 3 4 5 6 7 8 9
>Mapped:   2 8 7 3 9 1 4 6 5
> 
>2) There are 9! such mappings, producing a Basic Set [Defined Term]
>of 362,880 solutions.

You are right so far.

>3) Within each solution in the Basic Set it is possible to permute
>the rows and columns of each minor (3x3) square.  For example, rows
>1,2 and 3 can be permuted six ways, as can columns 1,2 and 3.
>Similarly, the other two sets of rows and the other two sets of
>columns can be commuted in the same way.

Right again.

>These permutations can be combined in 6 to the power 6, i.e., 46,656 
>ways.  I believe, but cannot prove, that any such combination will 
>not match any other such combination or any member of the Basic Set.

I'm not so sure that I would believe that.  In fact, I would bet that
there are some solutions that could be permuted in one of those 6^6
ways to get the same now solution as if you permuted the numbers in
one of those 9! ways.  But I think that there are some solutions where
this could not happen.

>4) Hence I reckon there 362,880 x 46,656, i.e., 16,930,529,280 unique 
>Sudoku puzzles.

And here is where you have underestimated the most.  You are assuming
that every Sudoku puzzle can be permuted in one of your 9!*6^6 ways
into a single solution.  In fact, there are many different solutions
that cannot be permuted to one another.  But it takes a lot of work to
find even one solution in each collection of 9!*6^6.

You can find some papers that have been written on this subject at

    http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf 

and

    http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html 

The first paper says that there are about

  6.6709 * 10^21

valid Sudoku grids.  Much of the work of computing this number was
done on the computer, although the computer certainly can't list off
that many grids; it would take forever.  But it did a lot of the
checking before complete determinations could be made.

The second paper says that two grids are "essentially different" if
they cannot be mapped to one another by one of the transformations
you described, as well as four others (permuting the three blocks of
three rows, permuting the three blocks of three columns, reflecting,
and rotating).  It finds that there are 5,472,730,538 essentially
different Sudoku grids.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 03/05/2006 at 21:16:00
From: Neville
Subject: Thank you (The Number of Possible Sudoku Puzzles)

Dear Dr. Vogler,

I wish to thank you very much for your prompt reply and constructive
criticism of my attempt to count the number of possible Sudoku puzzles.

You pointed out that I had neglected to consider the possibility of
permuting the rows and columns in groups of three.  Actually, this
thought occured to me after I had submitted my question.  The net
effect would have been to inflate my estimate by a factor of 36 and
apparently it was already too large.  Thank you for the help.

Sincerely, 

Neville

P.S. By the way I am probably a little older than the average
correspondent to Dr. Math, as I'll be 75 next month.  I take these on
to preserve gray matter.  Thanks again!