How can I generate Sudoku puzzles?

Question

I'm trying to make a Sudoku puzzle generator. It's a lot harder than I expected and the more I get into it, the harder it gets!

My current approach is to split the problem into 2 steps:

1. Generate a complete (solved) Sudoku puzzle.
2. Remove numbers until it's solveable and has only 1 solution.

In step 1, since I'm using a brute force methods, I'm facing some run time issues. Is there an optimal way of filling in a complete Sudoku puzzle?

In step 2, what kind of algorithm should I use to "puzzlize" a solved sudoku?

Answer 1

I have a top selling Sudoku game on the iOS app store. Here's how I generated puzzles.

First I do have a puzzle generator application. But it's not part of the game's code. It' is a stand alone app that I use to make puzzles. It's highly modified so I can set it to create different pattern types, difficulty ratings, number of givens, etc. Generating puzzles and getting a consistent difficulty level is hard to do on the fly and takes more time than a player would want to wait. So, I generate what I call "seed puzzles" and that is what is used by the game's code to generate the puzzles that people play.

I'm not answering how to code a generator here. You can google and find tons of puzzle generator code online. Start there. But to make a good game you need to make a good game. My game does not generate puzzles on the fly.

The way my puzzle generator app works is that it generates thousands of puzzles per minute, but they're not all good and they don't all match a specific difficulty rating. The generator creates a puzzle, then solves it and figures out a difficulty rating, and scores the puzzle based on the techniques needed to solve the puzzle, and determines if guessing is required to solve it (which is usually bad). It tosses out any puzzles that don't match a criteria. For hard but not impossible puzzles, on a fast machine, it can take an hour to generate 100 puzzles that match my exact specifications. This is why I don't do this in the app. Generating puzzles on the fly with those tough specifications wouldn't work for the quality of puzzles that I have in my app. So I run that app in 10 windows at a time all night to get the number of puzzles I need.

The puzzles are strings, 162 characters long, 81 characters with numbers and dashes or dots where the blanks are going to be, then another 81 with the solution. Then columns for each of the stats, like how many singles, doubles, etc.

My output from all the generation sessions are comma delimited lines with the stats as columns. I'll take maybe 10,000 puzzles, bring them in to excel, and sort them by difficulty. Then bring them into an app to see them on the game board. I also look at them for visual appeal and the visible patterns to the puzzle. Then I hand pick from those.

I call them seed puzzles and here's what I mean. The numbers in a sudoku game are really just tokens. Instead of being the numbers 1-9 they could be colors or symbols or letters. So my seed puzzles are not numbers they are the letters a-i. Each seed puzzle gets changed on the fly to make a playable puzzle:

1. Randomize the numbers/tokens. When I turn the letters a-i back to into the numbers 1-9 the lookup table is randomized. Meaning that a isn't always 1. That alone creates about 300,000 variations on each puzzle.
2. Rotate the puzzle by 90, 180 or 270 degrees. That adds 4 more variations.
3. Flop the puzzle horizontally, vertically, or both. That adds 4 more variations.

Each seed puzzle therefore can create 5,806,080 variations. I've tested this in the field with real players. People do not know they're essentially playing the same puzzle. It's impossible actually. Only if they were to notice that the pattern the givens are in are the same each time. But with even 100 different seeds no one will notice. A million users of my game haven't. I've also tested it with solver apps. A solver app won't solve a puzzle the same way when it's rotated or flopped. It will even sometimes analyze it as a different difficulty rating even though it's technically the same puzzle.

However, Big Bad Sudoku Book has 10's of 1000's of seed puzzles in 5 difficulty levels, and multiple puzzle patterns types. This means that there are billions of puzzles in my game. With every 10,000 seed puzzles there are 58,060,800,000 different puzzles.

In Sudoku Book version 4 (due out 2016) I figured out a way to be able to specify an exact puzzle out of those 58 billion and get the same puzzle on each player's device.

Answer 2

In step (1) Generate a complete (solved) Sudoku puzzle, since I'm using a brute force method, I'm facing some run time issues. Is there an optimal way of filling in a complete Sudoku puzzle?

There is an easy way to fill in a complete Sudoku puzzle - group filling and circular shift.

1. Fill the first row with nine different numbers.
2. Fill the second row which is a shift of the first line by three slots.
3. Fill the third row which is a shift of the second line by three slots.
4. Fill the fourth row which is a shift of the third by one slot.

line 1: 8 9 3  2 7 6  4 5 1
line 2: 2 7 6  4 5 1  8 9 3 (shift 3)
line 3: 4 5 1  8 9 3  2 7 6 (shift 3)

line 4: 5 1 8  9 3 2  7 6 4 (shift 1)
line 5: 9 3 2  7 6 4  5 1 8 (shift 3)
line 6: 7 6 4  5 1 8  9 3 2 (shift 3)

line 7: 6 4 5  1 8 9  3 2 7 (shift 1)
line 8: 1 8 9  3 2 7  6 4 5 (shift 3)
line 9: 3 2 7  6 4 5  1 8 9 (shift 3)

To prevent the user from noticing the obvious pattern, it might be a good idea to randomize the order of the rows and the columns so that there no longer is any pattern. So long as all 9 numbers in each row/column move together as one atomic unit, the Sudoku board will always remain valid.

You get a complete filled Sudoku puzzle. For more details, you can search "make Sudoku".

Answer 3

It's not too difficult, provided that you have a sudoku solver.

Making sudoku solvers is a hard / interesting problem, so it's best to save it for a different question. Or you can just read this and see how you go.

1. To generate a solved puzzle, simply run the solver on an empty board. The only caveat is you should randomise the "guesses" that the solver uses, otherwise you might end up with the same puzzle every time. That is, at some point the solver will try a number for a cell; it might try it in this order: 1, 2, 3, 4, ... and pick the first one that works. You need to shuffle that order so that it tries, say, 4, 7, 2, 9, .... This process should be as fast as your solver.
2. To remove numbers, use this algorithm:
   • Pick a random number you haven't tried removing before
   • Remove the number, run your solver with the added condition that it cannot use the removed number here
   • If the solver finds a solution, you can't remove the number
   • Repeat, until you have removed enough numbers (or you can't remove any more)

This is a very simple (and naive) method, so there's no guarantee that you'll get puzzles of a certain difficulty - aside from the number of missing numbers that is - or if you can even remove the amount of numbers you want. Hope this helps anyway.

Answer 4

I just think its interesting to point out this webpage, since it helped me a lot for our proyect development. Making a sudoku with an unique solution is far away from a simple task. In the link you can find how the author (he really did a great job, its no me eh!), found several different strategies. You can have an idea to generate your own Sudoku solver.

Now, going with the topic, there is also a way to generate similar sudokus, just by

1. The permutation of the rows.
2. Other simple solution, is to start with a fill out sudoku of minimun 17 digits fill in (its the proven minimun to find a unique solution), and fill in following diferent strategies (e.g. in the previous link the strategies are divided on difficulties, you can do something similar), till you reach the unique solution.
3. There was a list of a mathematician trying to find a 16 starting digit unique solution sudoku, with a HUGEEEEEE list of 17 digits sudokus. I cant remember if he has any kind of copy write, but Im pretty sure, if you can offer him other 17 unique solution sudoku will be more than glad to let you use his data.

Cheers and good luck with the algorithm :D

Answer 5

My solver is using brute force, and can find solution within 20 milliseconds. By using the deletion method, described above, my generator produces a puzzle within 200 milliseconds.

It usually generates a puzzle with around 24-34 digits left, and I still don't know how in the world they manage to produce 17-digits puzzle.