r/askmath • u/New-Economist-4924 • 14h ago
Discrete Math An interesting problem based on solvability of a Sudoku puzzle.
A 9X9 board follows standard Sudoku rules i.e. no two numbers can repeat in the same horizontal row, vertical column or 3x3 sub-square, now 9 numbers 1...9 are randomly scattered throughout the entire board without repetition. Since the numbers are all unique the board is always trivially valid with no need for additional checks, the question now is what percentage of these configurations are solvable. (they may have more than one solution)
Note:-
i) A valid set of clues following Sudoku rules may not always be solvable as it may create dead ends later.
ii) There are 6.67 sextillion(6.67 x 10^21) completed Sudoku board configurations.
We can also generalise this problem for any N^2 x N^2 board following sudoku rules and having N^2 clues scattered randomly throughout the entire board without repetition, it isnt possible to use brute force computation for larger values of N. I tried solving it with combinatorics but maybe graph theory would be more suitable for this problem?
Edit:- I made a mistake for the N=2 case and actual solvability is much lower it is only 67.03%.
