# How can I generate Sudoku puzzles?

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?

-
this question has some info you can extract in how to generate puzzles – ratchet freak May 25 '13 at 14:48
This question has also been asked on Puzzling (and has better answers there): puzzling.stackexchange.com/questions/142/… – congusbongus Aug 11 '14 at 4:30

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.

-
Very usefult post. Do you in any way check if seeds that you generate can be created from other seeds, meaning that you have identical seeds? – VLAS Feb 5 at 20:50
Yes. I drop them all in textmate and do a sort. Then remove duplicates. I don't think it's ever removed any. Seeds are absolutely unique. It's impossible to make the same puzzle from two different seeds. Someday I'll show the exact process but not now when I'm still profiting off my methods. :) – badweasel Feb 5 at 21:27
Actually my entire process is pretty much here. – badweasel Feb 5 at 21:28
+1 for the insight that the numbers are just tokens and the way you can make variations is just change the numbers assigned to the letters. – S. Mitchell Feb 21 at 17:17

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.

-
Make sure the solver can't find multiple solutions from the same state. Normally there should be only one solution. Also, you can check which logical steps the solver needed to take to find the solution to determine the difficulty, e.g. did it need to use the x-wing strategy or ...? – OriginalDaemon Jun 5 '14 at 8:50
@OriginalDaemon regarding your first point, it's covered in the third dot point: if removing that number results in a second solution, go back. – congusbongus Jun 5 '14 at 10:38

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

-
Hmm, the link is for sudoku solver, not generator. – greenoldman Jan 14 '15 at 13:36
@greenoldman YES, ITS A SOLVER. I think its interesting for the user since he's current method its to remove a number, and solve. The link gives strategies for solving faster he's partials sudoku's – David Sánchez Jan 15 '15 at 2:14