11
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ remove a number and test if the solution is still unique, repeat until dead end $\endgroup$ – ratchet freak May 15 '14 at 21:18
  • 3
    $\begingroup$ @ratchetfreak ... so how do I test if the solution is still unique? That's the question. :P $\endgroup$ – Doorknob May 15 '14 at 21:18
  • 2
    $\begingroup$ fire a solver at it that can test for multiple solutions of course :) $\endgroup$ – ratchet freak May 15 '14 at 21:19
  • $\begingroup$ Find the code for an efficient solver and reverse it. $\endgroup$ – Kevin May 15 '14 at 21:39
9
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ This works, but it's highly inefficient. Surely there's a more effective technique? $\endgroup$ – Kevin Jun 8 '15 at 16:45
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The last approach is what I would do. Generate symmetrical patterns with random numbers and run a sudoku solver that can check that the sudoku is possible and unique, and measure the level of difficulty. $\endgroup$ – Florian F Oct 12 '14 at 20:33

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.