Wednesday, July 1, 2009

Sudoku Puzzle Generating, Pragmatic Way

Couple of days ago I described how you could generate a good random sudoku field, today I'm going to advocate for just opposite thing. There's no controversy in really, just there are different cases, when you should and when you should not do that.

You should or could write your own sudoku puzzles generator if you are particularly interested in the field and ready to spend lots and lots of time, getting deep in all the various rules which actually make a good sudoku. Well at least it will keep your self-esteem up.

But if you are just writing some implementation of the sudoku game, you actually better not to do that. And here is why.

  • Sudoku generating is a random process with generally unpredictable duration. There is a good chance that your generator will get unlucky and stuck. And a hanging over application is the last thing you want your user to see.
  • The process of generating of a really good, hard sudoku usually takes time, sometimes a few seconds
  • There are lots of rules you need to get into, implement test over, and then if you are not an expert in sudoku you wont be able to check it out if you have done everything properly
  • You will probably forget and never use again all the knowledge you gain during the implementation. I don't want to call it a waste of time, but I'm pretty sure there are better ways to actually waste your time.
  • A good sudoku generator might be quite big and complicated piece of software, which will be hard to test and support.

Luckily there are better ways to do that. Use other people's work to be precise. There are lots and lots of online sudoku generators, or you could use any desktop applications, most of them cache boards in files. I used the gnome-sudoku application, it lets you generate any number of sudoku and saves them in the files in the gnome configuration directory, or you can grab my archive right here puzzles.zip

What about the number of puzzles ask you? You need some storage to keep them and have big enough collection to keep the user happy.

Actually not, and here is the trick of the article. You actually can keep just a few puzzles for each level and then generate new puzzles out of the originals. You can safely do the following things with your puzzles

  • Rotate them
  • Flip in any way
  • Randomly shuffle rows and columns inside the 3x3 boxes
  • Shuffle rows and columns of the 3x3 boxes

As the result, if you say have initially a collection out of 16 puzzles, then you can rotate and flip it in 5 ways, then you can shuffle rows and columns in 9 ways in each of the nine 3x3 boxes, and eventually you can have 9 combinations of the 3x3 blocks.

16 * 5 * 9 * 9 * 9 = 58320

That's more than enough for your user never see the same puzzle twice in a row. More of that, all of those puzzles will be really consistent by the difficulty level because initially it is just the same puzzle.

And for the end you can see a possible JavaScript implementation right here boards.js

This is pretty much it. Have a good one!

No comments: