Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sudoku generator

  1. Feb 14, 2008 #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.
  2. jcsd
  3. Feb 14, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  4. Feb 15, 2008 #3
    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.
  5. Feb 15, 2008 #4


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook