# Random Sudoku generator

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?

• This looks like a viable solution: dryicons.com/blog/2009/08/14/…
– Joe
Commented Mar 7, 2012 at 6:36
• There is now a meta question regarding this. Please discuss there or in chat. Commented Mar 7, 2012 at 16:03

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:

1. Permutations of digits
2. Permutations of rows (the bands and the rows inside each band)
3. Same thing for columns
4. 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)

• But Justin is asking for a way of generating an incomplete puzzle such that there is a unique way of completing it. Even if you generate a 9x9 grid satisfying the Sudoku constraints, it's not clear why removing a specific subset of the cells would give you a puzzle that can be completed in a unique way. Commented Mar 8, 2012 at 21:32
• @Janoma: oh, my bad, I will edit. But it is not very meaningful if one does not define what a proper puzzle is. (Is a grid with only one empty cell a puzzle?). Do we want a minimal grid, (i.e. if you remove a digit the solution is not unique anymore?) That's an interesting question.