patternModerate
Random Sudoku generator
Viewed 0 times
randomsudokugenerator
Problem
I want to generate a completely random Sudoku.
Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a unique way to complete it to match the Sudoku constraints (each line, column and aligned $3\times3$ square has no repeated element) and it is minimal in that respect (i.e. if you omit any more element the puzzle has multiple solutions).
How can I generate a random Sudoku puzzle, such that all Sudoku puzzles are equiprobable?
Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a unique way to complete it to match the Sudoku constraints (each line, column and aligned $3\times3$ square has no repeated element) and it is minimal in that respect (i.e. if you omit any more element the puzzle has multiple solutions).
How can I generate a random Sudoku puzzle, such that all Sudoku puzzles are equiprobable?
Solution
Generating the exact uniform distribution of all sudoku puzzles can be done that way: you can just randomly generate a 9x9 grid and then only keep it if it is a correct sudoku grid, otherwise retry.
This brute-force approach guarantees you a uniform distribution but is clearly not efficient, since you can multiply the probability of the grid to be correct by $9^{17}$ only by generating a random 8x8 grid and then fill the remaining two lines. This is still a random distribution, but still way too inefficient.
You can also force the first line to be $[1, 2, .. 9]$, then randomly generate the remaining of the grid and then randomly pick a permutation of all digits. You will still pick all the grids with the same probability but $9!$ faster.
Maybe you see where I am going: answering this problem in a clever way will probably lead you to wonder about the underlying symmetries of sudoku grids. A lot of work was done in this direction to prove the fact that 17 is the minimal number of clues to a sudoku (see this article) and you can go here to see this precise enumeration of 5,472,730,538 classes of 3,359,232 similar grids, which uses these symmetries:
With this framework you can pick randomly one of the 5,472,730,538 classes (they can actually be compressed into 6 GB) and then pick one of the representative for each symmetry, respectively one in $9!, 6^4, 6^4, 2$.
EDIT: to adapt this to incomplete puzzles, you can choose randomly a subset of your grid, check if the solution is unique with a sudoku solver and retry if not. This is not a uniform distribution since the number of incomplete puzzles with a unique solution may be different for two grids. (I would be very surprised otherwise)
This brute-force approach guarantees you a uniform distribution but is clearly not efficient, since you can multiply the probability of the grid to be correct by $9^{17}$ only by generating a random 8x8 grid and then fill the remaining two lines. This is still a random distribution, but still way too inefficient.
You can also force the first line to be $[1, 2, .. 9]$, then randomly generate the remaining of the grid and then randomly pick a permutation of all digits. You will still pick all the grids with the same probability but $9!$ faster.
Maybe you see where I am going: answering this problem in a clever way will probably lead you to wonder about the underlying symmetries of sudoku grids. A lot of work was done in this direction to prove the fact that 17 is the minimal number of clues to a sudoku (see this article) and you can go here to see this precise enumeration of 5,472,730,538 classes of 3,359,232 similar grids, which uses these symmetries:
- Permutations of digits
- Permutations of rows (the bands and the rows inside each band)
- Same thing for columns
- Transposition
With this framework you can pick randomly one of the 5,472,730,538 classes (they can actually be compressed into 6 GB) and then pick one of the representative for each symmetry, respectively one in $9!, 6^4, 6^4, 2$.
EDIT: to adapt this to incomplete puzzles, you can choose randomly a subset of your grid, check if the solution is unique with a sudoku solver and retry if not. This is not a uniform distribution since the number of incomplete puzzles with a unique solution may be different for two grids. (I would be very surprised otherwise)
Context
StackExchange Computer Science Q#72, answer score: 16
Revisions (0)
No revisions yet.