Sudoku grid guaranteed to be solvable?

Question

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?

Answer 1

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.

Answer 2

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.