13
$\begingroup$

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?

$\endgroup$
15
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Janoma Mar 8 '12 at 21:32
  • 1
    $\begingroup$ @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. $\endgroup$ – jmad Mar 8 '12 at 21:59
  • $\begingroup$ "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. $\endgroup$ – Janoma Mar 8 '12 at 22:03
  • $\begingroup$ @Janoma, jmad: a valid puzzle is normally minimal, I forgot to mention that. $\endgroup$ – Gilles Mar 8 '12 at 22:22
  • $\begingroup$ @Gilles Is that a definition? I wonder if that is indeed the intended meaning of the OP. It makes the problem much more difficult :-) $\endgroup$ – Janoma Mar 8 '12 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.