There are 6670903752021072936960 Sudoku grids
Bertram Felgenhauer and Frazer Jarvis
This page contains details of the enumeration of Sudoku grids. See
www.sudoku.com for
more details. The algorithm is a brute force count: all programs were written by
Bertram Felgenhauer,
incorporating several ideas of mine which reduce considerably the size of
the brute force search.
We have written a short article, which is now available.
In addition, this page contains a program due to Ed Russell which independently
verified the original calculations. (Thanks to Ed for allowing us to make
this available on this page.)
Bertram Felgenhauer's programs and data
Programs to reduce the configuration list
- sudoku.hs: a Haskell program which reduced
the configuration list from 36288 to 306. [Now obsolete]
- sudoku_equiv.cc: a C++ program which
refines the earlier idea, with a more effective data structure to store
the equivalences, thus reducing the number of equivalence classes from
36288 to 71.
- sudoku_verify.py: a Python program
to verify the reduction to the 71 classes.
Reduced list of configurations
- jobs1.txt: the job list for the 306
configurations produced by the Haskell program (this was Bertram's
original calculation, which first gave the result).
- jobs2.txt: the job list for the 71
configurations produced by the C++ program.
- tree.txt (2133KB),
gzipped version (263KB):
longer output from sudoku_equiv.cc,
documenting how the 36288 configurations are related. The Python program
takes this as its input, and verifies that the rules were applied
correctly.
Program to count number of completions of a configuration to a fill grid
- sudoku2.cc: given a configuration produced
in the above list, this program counts (by means of an exhaustive
search) the number of completions to a full Sudoku grid.
Results
Ed Russell's program and data
- equiv.c: a C program which independently
verifies the results of the above programs. (Note that the output of the
program is given as a comment at the start of the file.)
Additional pages of data