9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This seems to be an open problem. Here's a significant result: nature.com/news/… $\endgroup$ – Edward ffitch Jul 4 '14 at 18:17
  • $\begingroup$ Upper bound is $2^{81} \cdot 6,670,903,752,021,072,936,960$ $\endgroup$ – NovaDenizen Jul 4 '14 at 18:19
  • $\begingroup$ 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). $\endgroup$ – Peter Woolfitt Jul 4 '14 at 18:20
  • $\begingroup$ 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. $\endgroup$ – Robert Soupe Jul 4 '14 at 19:40
4
$\begingroup$

Due to Felgenhaur and Jarvis

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

and Fangying, Mengshi, and Aslasksen

(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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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