# How many Sudoku puzzles are there with at least one solution?

A Sudoku puzzle is a 9 by 9 matrix of blanks(which we can represent as 0), and elements of the set {1,2,3,4,5,6,7,8,9}. How many Sudoku puzzles are there with at least one solution. Yes, I am even counting grids with no blanks.

• This seems to be an open problem. Here's a significant result: nature.com/news/… – Edward ffitch Jul 4 '14 at 18:17
• Upper bound is $2^{81} \cdot 6,670,903,752,021,072,936,960$ – NovaDenizen Jul 4 '14 at 18:19
• Let $S$ be the number of solutions states. Then we can bound the answer to your question above by $S(\binom{81}{0}+\binom{81}{1}+\cdots+\binom{81}{81})=2^{81}S$. By Felgenhauer and Jarvis $S\approx 6.671\times 10^{21}$ (they do give an exact number). – Peter Woolfitt Jul 4 '14 at 18:20
• Just a side note: the typical number of givens is 17, which I believe as a minimum is a necessary but not sufficient condition to ensure a unique solution. I haven't done many sudokus, but alas! I have done a couple with two possible solutions that were published in national periodicals. – Robert Soupe Jul 4 '14 at 19:40

Due to Felgenhaur and Jarvis

(see their paper here: http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf)

(see their paper here: http://www.math.nus.edu.sg/aslaksen/projects/SHI-ZHANG_Sudoku.pdf)

we know that the total possible number of legal 9x9 Sudoku enumerations is $N_{\text{enumerable}}=6670903752021072936960$.

I will provide an upper bound to the number of puzzles with at least one solution solution, $N_{\text{solvable}}$.

Summing up the number of ways we can replace $n$ squares on a given enumerated grid with $0$'s, and then multiplying by the number of legal grids gives

$$N_{\text{solvable}}<N_{\text{enumerable}}\cdot\sum_{n=0}^{81}\binom{81}{n}=6670903752021072936960\cdot2^{81}=16129255571964761146444296776129424146741329920\approx1.62\times10^{46}$$

This is only an upper bound because it will certainly be an over-count (this is easy to see), so I welcome any refinements to this upper bound as edits below my post.

• Sorry, I see that this was posted as a comment while I was typing this out. My apologies @Peter Woolfitt ! – user155385 Jul 4 '14 at 18:25