Search code examples
pythonalgorithmmathdiscrete-mathematics

Counting problem: possible sudoko tables?

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: (*)
alt text
(source: sitmo.com)

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) .... =
alt text
(source: sitmo.com)

3- finally multiply the result by 9! (permutation of 1s-2s-3s...-9s in (*))
alt text
(source: sitmo.com)

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

Solution

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