Efficiently Generating Sudoku Puzzles by Difficulty

[Doom of Doom]

I was wondering if there was a more efficient way of generating sudoku puzzles.

I already have a method to create puzzles of varying difficulties that goes something like this:
- Randomly generate a completed 9x9 solved sudoku
- Randomly remove some of the numbers from the matrix (as determined by the desired difficulty; more difficult means more are removed)
- Solve the puzzle using a logic method
- If more complex logic is needed to solve the puzzle, assign higher difficulty values
- If the final difficulty value is within the desired range, then the puzzle is good
- Else, start over.

This works, but is there a better way to more efficiently generate sudoku puzzles based on difficulty? I am trying to develop an algorithm that starts with an empty puzzle, then systematically fills in squares. The system in which it fills in squares should be different for varying levels of difficulty.

 

[chroot]

Seems like your first two steps could be replaced with these:

- Start with an empty Sudoku
- Add a few random numbers in such a way that keeps it consistent

The rest of the steps could then be followed as given.

- Warren

 

[Andre]

You may underestimate the complexity of sudoku a bit.

Sure, it's simple to generate the solution, albeit there are many sudokus with higher complexity like X-soduku, disjoint group sudokus and disjoint group X-sudokus. That's much more fun.

But generating algoritms for the puzzle from that is not that simple. Certainly not at random. There are redundant numbers and key numbers. If you delete numbers at random you may have to stop at ~30 - 35 filled cells remaining to have a simple solution in basic soduku whereas selecting only key numbers this may reduce to some 22 filled cells. if you allow the higher solution techniques, like hidden and naked pairs (waiting for jesters) the number of filled cells may drop to 17-18 for the very advanced and still have a single solution.

 

[-Job-]

Finding a solution to a given variable sized sudoku is actually an NP-Complete problem so it's one of those computer-intractable problems.

Generating an instance of a k*k sudoku should be much much easier (not to say that it's easy or immediately obvious). You should be able to find libraries or code examples for generating sudoku games on the internet.