Removing numbers from a full sudoku puzzle to create one with a unique solution

Question

What is a simple and efficient way of removing numbers from a full sudoku puzzle to create one with a single unique solution?

I have already figured out how to generate sudoku grids, like this one:

5 6 7 2 3 8 1 4 9 
4 8 9 7 6 1 3 5 2 
2 3 1 9 5 4 6 8 7 
1 7 5 6 8 9 2 3 4 
8 4 3 1 2 5 9 7 6 
9 2 6 3 4 7 5 1 8 
3 9 4 8 1 6 7 2 5 
7 1 8 5 9 2 4 6 3 
6 5 2 4 7 3 8 9 1 

Now, I need to make it an actual puzzle by removing some of the numbers. How can I do this in a simple and efficient way (that can be done by a computer)?

Answer 1

Here's how to remove numbers from a full Sudoku puzzle to create one with a single unique solution:

1. Remove a number,
2. Run a solver,
3. Check if the puzzle is still unique,
4. Repeat until solver is unable to find a solution, or solution is not unique.

Answer 2

Strictly speaking, you don't need to do anything because the puzzle already has a unique solution. Let's redefine your goal. Starting with a valid number grid, you want to eliminate numbers to arrive at a puzzle that still has a unique solution, but also has a specified level of difficulty (e.g., "Easy", "Medium", "Hard", etc.) and (optionally) has a symmetrical arrangement of numbers.

To do this, it helps to have a sudoku solver that can also tell you (a) if a puzzle has more than one solution, and (b) how difficult it is to solve. I'm using Bill DuPree's sudoku solver here, although you will get faster results using a solver that aborts as soon as it finds more than one solution instead of going on to count them all.

As others have suggested, a simple approach is to remove as many numbers as possible from the grid without losing the uniqueness of the solution. You will always get an empty top row if you clear the cells in strict sequential order, so you'll need to check them randomly. This is what I ended up with:

. 6 7 2 . . . 4 .
. . 9 . . 1 3 . .
2 . . . . . . 8 .
. 7 . . 8 . 2 3 .
8 . 3 . . . . . .
. . 6 . 4 . . . .
. . . . 1 6 7 . 5
. . . 5 . . . . .  24 numbers
. . . . . . 8 9 .  Difficulty: ultra-diabolical

We can get a symmetrical puzzle by clearing two cells at a time (cells n and 80-n), resulting in the following grid:

. 6 7 . . . . . .
4 . . . . 1 . 5 .
2 . . 9 5 4 . . 7
. . . . 8 . 2 . .
. . . 1 2 5 . . .
. . 6 . 4 . . . .
3 . . 8 1 6 . . 5
. 1 . 5 . . . . 3  27 numbers
. . . . . . 8 9 .  Difficulty: easy

Or, with a different random seed:

5 . . . 3 8 . . 9
4 . . . 6 . . . .
. 3 . . . . 6 . .
1 . 5 6 . 9 . . 4
. 4 . . . . . 7 .
9 . . 3 . 7 5 . 8
. . 4 . . . . 2 .
. . . . 9 . . . 3  28 numbers
6 . . 4 7 . . . 1  Difficulty: ultra-diabolical

As you can see, this approach results in puzzles with widely varying difficulty levels. To get a puzzle with a particular difficulty level, you can simply repeat this process with different random numbers until you get a result you like. (Using a hill climbing algorithm might make this process more efficient, although I haven't looked into this.)

Another approach

Instead of removing numbers from a completed grid, you could try adding numbers to a minimum sudoku puzzle (i.e., a puzzle with a unique solution but only 17 filled cells). Even after filling cells to make these puzzles symmetrical, they should still be fairly challenging to solve.