Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 4:30

2 Answers 2

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.

share|improve this answer
    
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 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 at 10:38

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

First I do have a puzzle generator application. But it's not part of the game's code. It' is a stand along 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. 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 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 they lookup table is randomized. 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.

However, Big Bad Sudoku Book has 10's of 1000's of seed puzzles in 5 difficulty levels, and multiple puzzle patterns types.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.