Jesper Niedermann's .NET Blog
about .NET and related technologies RSS 2.0
# Monday, 03 August 2009

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:

s1

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:

s2

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.

Monday, 03 August 2009 22:16:48 (GMT Daylight Time, UTC+01:00)  #    Comments [5] -
Games & Puzzles
Tuesday, 04 August 2009 11:25:47 (GMT Daylight Time, UTC+01:00)
Very well done - I like your thinking outside the box to generate sudokus so fast :)
Sunday, 09 August 2009 10:18:53 (GMT Daylight Time, UTC+01:00)
Hi Jesper

Nice work... but I'd really really like to somehow have the option to only create sudoku's that are guaranteed solvable.

Should be really easy to write that algorithm, I think... :-)
Monday, 10 August 2009 20:02:07 (GMT Daylight Time, UTC+01:00)
Hi Jan,

I will of course give the "Sudokus have to be solvable algorithm" a thought, but I will not sacrifice speed. So I will prefer an algorithm that is true 99% of the time if it is fast.
Tuesday, 03 August 2010 15:51:43 (GMT Daylight Time, UTC+01:00)
At generere sudoku'er der ikke har en entydig løsning er som at generere en krydsord uden løsning: totalt ubrugeligt.
Så er det altså ligegyldigt hvor hurtigt man kan gøre det.
Udfordringen i at generere sudoku'er er netop at have en "solver" som kan afprøve en sudoku for om den kan løses med de metoder der egner sig for mennesker.
Jeg har til brug for min "solver" brug for "svære" 36x36, men har kun kunne finde trivielle, som nærmest løser sig selv.
Per Troelsen
Tuesday, 03 August 2010 16:38:51 (GMT Daylight Time, UTC+01:00)
Hej Per,

Jeg går ud fra at du er med på at der altid ER løsninger til de sudokuer jeg genererer. Der er bare ingen garanti for at der kun er én. Dette gælder også sudokuer du køber i diverse blade og bøger. Dem der er kategoriseret som meget svære har typisk flere løsninger og man er på et tidspunkt nød til at gætte. På sin vis kan jeg kun være enig. En Sudoku med mere end en løsning anser jeg også som "ubrugelig". I den forstand at det ikke er sjovt at løse den når man skal gætte undervejs. Det føles som at snyde og man indser hvor formålsløst det egentlig er at løse sudokuer :)

Jeg vil tro at det vil være endog meget tidskrævende at generere vilkårlige sudokuer på 36x36 med præcis én løsning, og det vil ihvertfald ikke være muligt at give folk mulighed for selv at specificerer hvor mange "huller" de vil have, som jeg gør pt.

En dag hvor jeg keder mig kan det være jeg kigger på det igen.

BTW: Som du måske kan se af min blogtekst var min generator mere en algoritmisk udfordring end et forsøg på at underholde :)

Men du har simpelthen lavet en solver ?
Jesper
Comments are closed.
Archive
<2017 October>
SunMonTueWedThuFriSat
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234
About the author/Disclaimer
I am a software architect with focus on Microsoft Technologies. I have been working with these in different large companies since 1995. I am currently employed at UVdata A/S.
Here is my View Jesper Niedermann's profile on LinkedIn

Disclaimer
The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

Privacy policy
The privacy policy of this site.

© Copyright 2017
Jesper Niedermann
Sign In
Statistics
Total Posts: 28
This Year: 0
This Month: 0
This Week: 0
Comments: 32
All Content © 2017, Jesper Niedermann
DasBlog theme 'Niedermann' created by Jesper Niedermann, based on 'Business' created by Christoph De Baene (delarou)