As others have said, a sudoku problem is only valid if it has a unique solved grid. A sudoku generator will have to check that the partly emptied grid still only has the solution it was created from, that the removal of numbers hasn't introduced ambiguities. An example with 6 removals was shown earlier but it can happen even by removing 4 numbers:
Code: Select all
123 456 789
456 789 123
78. .31 456
31. .78 564
564 123 897
897 564 231
231 645 978
645 897 312
978 312 645
The blanks must be 2 or 9, but there are two ways to fill them.
Whoops! This is incorrect in the example you just gave... Because there's only one unknown in each 3x3 grid, you can deduce the missing numbers by looking at which digit is missing from that 3x3 grid.
The example you want is to take two rows (y1, y2) and two columns (x1, x2) in the grid (A) such that:
- floor(y1/3) = floor(y2/3)
- floor(x1/3) != floor (x2/3)
- A(x1, y1) = A(x2, y2), A(x1, y2) = A(x2, y1)
Now you have two distinct solutions for those four squares: because after the values there are blanked out, both of those values are missing from all rows, columns, and 3x3 grids from which a box was blanked.
I believe there is another problem with the approach distractedSofty proposed:
To answer the original question, the best way to generate a legal board (imo) is to have a 9 element list for each square, denoting the possible values the square could take. Then, randomly choose a value from the list for the first square, and update the lists in the same row, column and box to remove that value as a valid value. Repeat for the rest of the squares. No backtracking, and a predictable running time, obviating the need for a timeout. This is pretty much your algorithm, but with a constrained random function. (not great for solving, however).
Difficult Sudoku puzzles don't necessarily lend themselves well to this kind of approach. There may be cases where looking at a single point in terms of row, column, and grid does not yield a specific value for a square: But you can still solve the grid by various types of elimination. For instance:
Code: Select all
_ _ _ 3 _ 4 _ _ 7
_ _ _ _ _ _ _ _ X
_ 5 _ _ _ _ _ _ _
_ _ _ 2 _ 3 _ _ _
_ _ _ _ _ _ _ 5 _
_ _ _ 1 _ _ _ _ _
_ _ _ 4 _ _ _ _ 1
_ _ _ _ _ _ _ _ 2
5 _ _ _ _ _ _ _ _
With nothing more than the information above, you can locate all the missing '5's on the board. This is because X is the only place a 5 could possibly be on the right-most column of the board. (We don't know where the 5 in the bottom-right grid will be located, but we know it's in column 7!) But distractedSofty's algorithm will never create this sort of challenge. It will keep adding squares to the row, column, and grid of X until it makes the choice of X completely
obvious based on the digits whose positions are already exactly known.
Another approach might be to start with a full, valid grid and remove one digit at a time, checking (via a solve, I guess) that this doesn't introduce ambiguities into the puzzle... Or the puzzle generator could emulate how players solve the puzzles - remove a given digit only if there's some solver-heuristic that can be used to conclusively put that digit back again - basically generate, in reverse, the sequence of steps a player will use to re-populate the grid. This approach would also have the benefit of being easy to control the difficulty of the resulting puzzle (by picking the set of heuristics that is used to validate each step - and checking which ones were actually used over the course of generating the puzzle)...