Extremely fast Sudokus of any size programmed in silverlight 3

I must admit that I have never understood why it was fun to solve Sudoku’s. But as a programmer I was fascinated with the idea of making the perfect Sudoku puzzle generator algorithm from the very first time I heard of Sudoku. Of course I wanted to make it so general that it could not only make the boring old 9x9 sudoku. But sodukus of any size 4x4, 9x9, 16x16, 25x25 and so on…

This resulted in a .NET 1.1 WinForms program 4-5 years ago in which I could randomly generate all sudoku combinations from 4x4 to 36x36. I created an algorithm that started in the upper left corner and put in a random number then moving to the next square put in a new random number from the remaining numbers. This meant that the algorithm had to backtrack when coming to a deadend where no number was valid. This approach guaranteed that all possible Sudokus could be generated, but it was extremely slow. Well for 9x9 sudokus it was less than a second but for 36x36 sudokus it was around 16 hours :O)

A few weeks ago I thought it was time to try out Silverlight and make a small program to test Microsofts “new” programming platform, but I had to come up with an idea for a small program. And for some reason Sudoku popped up again.

And I came up with a novel idea for an extremely fast generator (try it here). It has been said that no ideas are new anymore and I am pretty sure that I am not the first to think of this since the algorithm is pretty obvious. I start with a valid Sudoku as a template and then apply transformations of the columns, the rows and the numbers themselves.

To generate a valid Sudoku I first generate the template. The template is generated by starting with 1 in the upper left corner and then counting upwards. Next I go to the 4th row and start in the second column counting from 1 again like this:

Next I go to the 7th row and the 3rd columm and so on. So I add 3 rows (the square root of 9) each time. In a 16x16 sudoku I add 4 rows each time. The final template is generated in a few milliseconds even in a 400x400 Sudoku. The final template for a 9x9 sudoku looks like this:

The template is itself a valid Sudoku.

Now I make the transformation using an observation I have made. In any valid Sudoku I can make another valid Sudoku by switching the columns within each block of 3 columns. As indicated in red colour for the first block above.

Secondly I can do the same for the rows.

And last I can transform the numbers themselves so that all 1’s are transformed to a number from 1 to 9. all 2’s are transformed to one of the remaining 8 numbers and so on.

I could also have applied a 4th transformation that switched the big blocks as columns and rows, but I don’t think that it will add much value.

In all this the entire puzzle can be generated in milliseconds for even extremely big Sudokus.

Try it out yourself at http://www.niedermann.dk/Sudoku/Sudoku.aspx

A few calculations

Now for some thoughts on completeness.

A 4x4 Sudoku has 4x3x2x3x2x2 = 288 possible combinations. Not counting combinations for empty tiles. In my original algorithm I was sure I covered all these combinations.

When using my new algorithm I can generate 2x2x2x2x4x3x2 = 384 possible transformations for a 4x4 Sudoku. This is more than the number of possible Sudokus. Which means that some of these transformations must result in the same Sudokus. And furthermore I do not know if there are Sudokus not covered by the transformations.

In a 9x9 Sudoku there are 1,83493E+21 possible Sudokus and I can generate 264.539.520 of those or 2.380.855.680 if I had used the extra big block transformations. Not complete at all, but on the other hand a very large amount of Sudokus and at lightning speed.

Empty tiles

A Sudoku isn’t really a Sudoku without the empty tiles left for the person to fill out.

I just generate the empty tiles by choosing them at random. This method could probably lead to either very boring Sudokus or Sudokus that are impossible to solve. One day I might device some clever algorithm for emptying tiles in a more interesting fashion :O)

Silverlight

My conlusions on this my very first silverlight project is that it is extremely easy to make something appealing in silverlight. On the other hand there are som downsides. It is difficult to communicate between different silverlight hosts. I can only pass strings. When you hit the print button I open another browser window. And I actually have to serialize the Sudoku Grid and deserialize it again in the print window.

Another downside is that is not really browser agnostic. I have tried with 3 browsers IE8, IE7 and Firefox 3.5. Right now the only one working properly is IE8. In IE7 the new browser I open for printing has no menu, and so you cannot really print :O) In Firefox the silverlighthost cannot be resized, which is apparently a known issue. But it is a problem in the Sudoku generator because I offer Sudokus of any size. This means that in Firefox only 4x4 and 9x9 Sudokus will look good.

BTW: The rendering of a very large Sudoku takes some time of course even though the generation is over in milliseconds.

For my next silverlight project I think I will try out Prism and also the Out-of-browser experience.