How to generate Sudoku boards with unique solutions
Here is the way my own SuDoKu program does it:
Start with a complete, valid board (filled with 81 numbers).
Make a list of all 81 cell positions and shuffle it randomly.
As long as the list is not empty, take the next position from the list and remove the number from the related cell.
Test uniqueness using a fast backtracking solver. My solver is - in theory - able to count all solutions, but for testing uniqueness, it will stop immediately when it finds more than one solution.
If the current board has still just one solution, goto step 3) and repeat.
If the current board has more than one solution, undo the last removal (step 3), and continue step 3 with the next position from the list
Stop when you have tested all 81 positions.
This gives you not only unique boards, but boards where you cannot remove any more numbers without destroying the uniqueness of the solution.
Of course, this is only the second half of the algorithm. The first half is to find a complete valid board first (randomly filled!) It works very similar, but "in the other direction":
Start with an empty board.
Add a random number at one of the free cells (the cell is chosen randomly, and the number is chosen randomly from the list of numbers valid for this cell according to the SuDoKu rules).
Use the backtracking solver to check if the current board has at least one valid solution. If not, undo step 2 and repeat with another number and cell. Note that this step might produce full valid boards on its own, but those are in no way random.
Repeat until the board is completely filled with numbers.
Unless P = NP, there is no polynomial-time algorithm for generating general Sudoku problems with exactly one solution.
In his master's thesis, Takayuki Yato defined The Another Solution Problem (ASP), where the goal is, given a problem and some solution, to find a different solution to that problem or to show that none exists. Yato then defined ASP-completeness, problems for which it is difficult to find another solution, and showed that Sudoku is ASP-complete. Since he also proves that ASP-completeness implies NP-hardness, this means that if you allow for arbitrary-sized Sudoku boards, there is no polynomial-time algorithm to check if the puzzle you've generated has a unique solution (unless P = NP).
Sorry to spoil your hopes for a fast algorithm!
Easy:
- Find all solutions with an efficient backtracking algorithm.
- If there is just one solution, you are done. Otherwise if you have more than one solution, find a position at which most of the solutions differ. Add the number at this position.
- Go to 1.
I doubt you can find a solution that would be much faster than this.
You can cheat. Start with an existing Sudoku board that can be solved then fiddle with it.
You can swap any row of three 3x3 blocks with any other row. You can swap any column of three 3x3 blocks with another column. Within each block row or block column you can swap single rows and single columns. Finally you can permute the numbers so there are different numbers in the filled positions as long as the permutation is consistent across the whole board.
None of these changes will make a solvable board unsolvable.