Counting problem: possible sudoko tables?

Question

Hi,
I'm working on a sudoko solver (python). my method is using a game tree and explore possible permutations for each set of digits by DFS Algorithm.

in order to analyzing problem, i want to know what is the count of possible valid and invalid sudoko tables?

-> a 9*9 table that have 9 one, 9 two, ... , 9 nine.

(this isn't exact duplicate by this question)

my solution is:

1- First select 9 cells for 1s: (*)

2- and like (1) for other digits (each time, 9 cells will be deleted from remaining available cells): C(81-9,9) , C(81-9*2,9) .... =

3- finally multiply the result by 9! (permutation of 1s-2s-3s...-9s in (*))

this is not equal to accepted answer of this question but problems are equivalent. what did i do wrong?

Answer 1

The number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer and Frazer Jarvis in 2005 to be 6,670,903,752,021,072,936,960.

Mathematics of Sudoku | source

I think problem with your solution is that deleting 9 cells each time from available cells does not necessarily create a valid grid. What I mean is just deleting 9 cells won't suffice.

That is why 81! / (9!)^9 is much bigger number than actual valid solutions.

EDIT:

Permutations with repeated elements

Your solutions is almost correct if you want all the tables not just valid sudoku tables.

There is a formula:

(a+b+c+...)! / [a! b! c! ....]

Suppose there are 5 boys and 3 girls and we have 8 seats then number of different ways in which they can seat is

(5+3)! / (5! 3!)

Your problem is analogous to this one.

There are 9 1s , 9 2s ... 9 9s. and 81 places

so answer should be (9+9+...)! / (9!)^9

Now if you multiply again by 9! then this will add duplicate arrangements to the number by shuffling them.

Answer 2

According to this Wikipedia article (or this OEIS sequence), there are roughly 6.6 * 10^21 different sudoku squares.

Answer 3

What you did wrong was the last step: you shouldn't multiply the answer by 9!. You have already counted all possible squares.

This doesn't help you much when counting the possible Sudoku-tables. One other thing you could do is to count the tables where the "row-condition" holds: that is just (9!)^9, because you just choose one permutation of 1..9 for every row.

Still closer to the Sudoku-problem is counting Latin squares. Latin square has to satisfy both the "row-condition" and "column condition". That is already a difficult problem and no closed form formula is known. Sudoku is a Latin square with the additional "subsquare-condition".