9
$\begingroup$

I want to generate random sudoku grids.

My approach is to fill the three 3x3 groups on a diagonal of the grid, each with the numbers 1-9 randomly shuffled. That looks e.g. like the grid below:

+-------+-------+-------+
| 5 6 4 | · · · | · · · |
| 1 7 2 | · · · | · · · |
| 9 8 3 | · · · | · · · |
+-------+-------+-------+
| · · · | 3 2 5 | · · · |
| · · · | 7 9 6 | · · · |
| · · · | 8 1 4 | · · · |
+-------+-------+-------+
| · · · | · · · | 1 5 9 |
| · · · | · · · | 3 2 7 |
| · · · | · · · | 6 4 8 |
+-------+-------+-------+

Then I let my sudoku solver process it until it finds a solution to fill all remaining gaps. The example above resulted in the filled grid below:

+-------+-------+-------+
| 5 6 4 | 9 3 7 | 2 8 1 |
| 1 7 2 | 5 4 8 | 9 6 3 |
| 9 8 3 | 1 6 2 | 4 7 5 |
+-------+-------+-------+
| 7 4 9 | 3 2 5 | 8 1 6 |
| 2 1 8 | 7 9 6 | 5 3 4 |
| 6 3 5 | 8 1 4 | 7 9 2 |
+-------+-------+-------+
| 8 2 6 | 4 7 3 | 1 5 9 |
| 4 5 1 | 6 8 9 | 3 2 7 |
| 3 9 7 | 2 5 1 | 6 4 8 |
+-------+-------+-------+

My question is if this approach is mathematically safe, i.e. can you prove me that when I fill my grid using the described approach (randomly assigning the first 27 numbers to fields in the groups on a diagonal line), there will be always at least one possible way to complete the grid from there on?

Or are there chances that the randomly placed numbers can interfere with each other and result in an impossible grid?

$\endgroup$
  • $\begingroup$ And, also nice to know, are there cases with more than one solution? $\endgroup$ – Paul Jan 21 '16 at 18:42
2
$\begingroup$

WLOG the top block is in the canonical order, because we can just relabel, as in 5 -> 1, 6 -> 2, … in your example. I'm not going to make that replacement through the rest of your grid, but will just pretend you started off like that.

+-------+-------+-------+
| 1 2 3 | · · · | · · · |
| 4 5 6 | · · · | · · · |
| 7 8 9 | · · · | · · · |
+-------+-------+-------+
| · · · | 3 2 5 | · · · |
| · · · | 7 9 6 | · · · |
| · · · | 8 1 4 | · · · |
+-------+-------+-------+
| · · · | · · · | 1 5 9 |
| · · · | · · · | 3 2 7 |
| · · · | · · · | 6 4 8 |
+-------+-------+-------+

Making minor-row swaps within one of the three major rows, or making minor-column swaps within one of the three major columns, doesn't change solveability of the sudoku. Therefore we may WLOG that the top-left entry of each of the three grids is 1, by rotating:

+-------+-------+-------+
| 1 2 3 | · · · | · · · |
| 4 5 6 | · · · | · · · |
| 7 8 9 | · · · | · · · |
+-------+-------+-------+
| · · · | 1 4 8 | · · · |
| · · · | 9 6 7 | · · · |
| · · · | 2 5 3 | · · · |
+-------+-------+-------+
| · · · | · · · | 1 5 9 |
| · · · | · · · | 3 2 7 |
| · · · | · · · | 6 4 8 |
+-------+-------+-------+

Similarly we may WLOG that the 5 of the middle block appears in one of two places:

+-------+
| 1 *   |
| ! *   |
|       |
+-------+

because if it's in any of the others, we can row/column swap it into one of those. The exception is if it's in the ! position, which is actually equivalent to the top *. This is because we may transpose the entire grid, and relabel the top-left block again, without affecting the middle block's 1 or 5 except in moving them to the correct positions.

Likewise (but without the option of reflecting this time, because that could mess up the middle block) we may WLOG that the bottom-right block's 5 is in one of three positions:

+-------+
| 1 *   |
| * *   |
|       |
+-------+

There are now $2 \times 7! \times 3 \times 7! = 152409600$ remaining cases, which are left as an exercise to the reader.

$\endgroup$
  • 1
    $\begingroup$ Your explanations seems nice to me, but I didn't get how you get the numbers in your last paragraph? $\endgroup$ – Byte Commander Jan 21 '16 at 15:34
  • 1
    $\begingroup$ There are 2 possible places for the 5 in the central block, and then 7! possible placements for the remaining numbers in that block. Then there are 3 possible places for the 5 in the bottom-right block, and 7! possible places for the remaining numbers in that block. $\endgroup$ – Patrick Stevens Jan 21 '16 at 16:41
1
$\begingroup$

I worked this out on paper by drawing a sudoku grid and putting down all the numbers for each individual digit place, column and row it could and couldn't be. As long as the programme you're using is 100% reliable, there'll will be at least one right solution to each 27 numbers in the diagonal. Sorry I can't give you a formula for proof, this sort of stuff I'm better at visualizing it.

$\endgroup$
  • $\begingroup$ That was my guess as well and running my program for a few hundred times without errors supports it, but I was looking forward to some proof... $\endgroup$ – Byte Commander Jan 21 '16 at 14:57
  • $\begingroup$ Sorry! Did give it my best shot! As a sudoku enthusiast, this is such a cool question that's been put up on this site. $\endgroup$ – Sophie Meaden Jan 21 '16 at 14:58

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.