sudoku probability

209 Views Asked by At

I have a completely filled in sudoku board. If the sum of all digits in each row, in each column, and in each block (the typical sudoku constraints) are all 45, what is the probability that the board is a valid sudoku solution? (part 2: is checking this condition, and an additional one that each digit 1..9 occurs exactly 9 times in the grid sufficient to determine that a grid is a valid solution?)

2

There are 2 best solutions below

0
On

Leaving aside part 1, which looks like a difficult question, for part 2 checking these conditions is not enough. For example, take any completed Sudoku board where one box matches this pattern:

$ \begin{array}{|c|c|c|} \hline 1 & 4 & a \\ \hline 2 & 3 & b \\ \hline e & d & c \\ \hline \end{array} $

If you swap the 1,2 and the 4,3 then you have not altered any row, column, or box sum. Nor have you changed the count of any digit. But you no longer have a valid grid.

$ \begin{array}{|c|c|c|} \hline 2 & 3 & a \\ \hline 1 & 4 & b \\ \hline e & d & c \\ \hline \end{array} $

0
On

One way to look at this is to ask what fraction of the order $9$ Latin squares are valid sudokus. These have one of each digit in each row and column, which is much more restrictive than summing to $45$ or even having the right quantity of each digit in the square. There are $5524751496156892842531225600$ order $9$ Latin squares, of which about $1.2 \cdot 10^{-6}$ are valid sudokus from the Wikipedia page.