Sudoku generator

  • #1
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.
 

Answers and Replies

  • #2
chroot
Staff Emeritus
Science Advisor
Gold Member
10,226
34
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
 
  • #3
4,465
72
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.
 
  • #4
-Job-
Science Advisor
1,146
1
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.
 

Related Threads on Sudoku generator

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
12
Views
819
  • Last Post
Replies
7
Views
12K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
11
Views
3K
Replies
8
Views
4K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
4
Views
2K
Top