# 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?

## 2 Answers

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. – Janoma Mar 8 '12 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. – jmad Mar 8 '12 at 21:59
• "Some elements can be omitted" is precise enough (i.e. "one or more" elements can be removed). For example, a valid puzzle with one empty cell can be completed in a unique way, while an empty puzzle can not, since there is more than one valid puzzle. Also, a completed valid puzzle can be completed in a unique (trivial, empty) way. The question about the minimal grid is also interesting, but different from this one. – Janoma Mar 8 '12 at 22:03
• @Janoma, jmad: a valid puzzle is normally minimal, I forgot to mention that. – Gilles 'SO- stop being evil' Mar 8 '12 at 22:22
• @Gilles Is that a definition? I wonder if that is indeed the intended meaning of the OP. It makes the problem much more difficult :-) – Janoma Mar 8 '12 at 22:25

First, you must have a sudoku solver. Apply the solver on an empty sudoku. That is to find a solution for a sudoku with no clues. Filling in numbers from top left to right bottom in order. Otherwise, there is a time issue. I don't know why. Anyway, it works very fast wait no time to have a completed sudoku puzzle. When you apply backtracking, shuffle the list of possible numbers for each position. Otherwise, you will get the same puzzle everytime.

Second, randomize a new list of all positions. That is a list of 81 positions in random order. According to this list of order, try removing numbers from the above puzzle. Everytime, you remove a number, you have to check if it has more than one solution. If it has more than one solution. The number should put back and try next position in the random list. This process continues until the end of list or you already has removed 64 numbers from the puzzle successfully. The number is 64 because somebody has proved that there is no sudoku with less than 17 clues with unique solution. This process is varies from 15 seconds to 2 minutes. Usually 30 seconds to get a sudoku puzzle.

Third, if you don't want to wait 30 seconds to 2 minutes for each sudoku puzzle, you may apply some mutations to the above sudoku. This includes switching rows and columns, rotating. You may also remap the numbers. For example, 1->2, 2->3...9->1. After rotating and remapping, no one will notice this is the original sudoku.

There is no way to know the generated sudoku puzzles are equiprobable.