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

Building off of user 155385's answer we can get a lower bound as well as tighten the upper bound. You need at least 17 clues to solve a sudoku puzzle, and it's believed (albeit not proven) that any more than 40 clues uniquely determine a solution (https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Maximum_number_of_givens).

If we trust this maximum value of 40, then a lower bound is $$N_{enumerable}*(\binom{81}{81} +\binom{81}{80} + ... + \binom{81}{41}) = N_{enumerable}*1208925819614629174706176$$

Where we are choosing grids with 81 clues filled in, then 80 clues filled in, and so on.

We can also sharpen the upper bound slightly to

$$N_{enumerable}*(\binom{81}{81} +\binom{81}{80} + ... + \binom{81}{17}) = N_{enumerable} * 2417851466759455344675448.$$ The ratio between lower and upper bounds here is almost exactly 1:2.

$\endgroup$

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.