Your opinion on this method for generating a full grid?

ravellock

Hi,

This is my first post on this forum although I've been reading the topics for a few weeks now. As like many of you, I've been busy trying to program a quick yet simple soduko generator. My main programming tool is Macromedia/Adobe Director (making me more of a Lingo-scripter than a programmer Smile

. So far I have been able to program a Sudoku generator which, at the moment, is very slow (it is based on the thread "A decent method for creating puzzles?"). Part of this is because the generation of a full sudoku grid.

I've been playing with an alternative idea which I used before to create small magic squares (4x4, 5x5,6x6) and I found to work really really well. I've not yet seen this idea mentioned on this forum so I thought I'd post it and hear what you think. It works likes this:

Step 1: I start with a set of arrays. All arrays combined contain all the combinations of a row (1,2,3,4,5,6,7,8,9). For instance, in a 4x4 square a row can be 1 of 24 combinations (4!). For a 5x5 magic square, a row may be 5! (120)combinations big. So for a sudoku-square (9x9 / 9!) all arrays combined is "362880 combinations" large. What I do is divide this large array of 362880 combinations into 9 arrays (so each array is 40320 combinations big?) The first array contains all combinations starting with "1", the second array with "2", etc. (I want to use a seperate program just to get the arrays so all the arrays are ready in step 1).

Step 2: Random-pick a combination from one of the arrays. Then "delete" (forget, whatever) the array. This combination is row1 from the magic square.

Step 3: Random-pick another combination from the remaining arrays. Check if it 'fits' : no number of this row may match the position of the numbers of the row above. And check per 3x3 square if every number is present only 1 time. If not, "delete" the picked combination from the array and random-pick another combination from an array. In case of a fit, this combination will be row2. Now "delete" this array.

Step 4: Repeat step 3 for the next rows untill the sudoku grid is filled.

I've tried this technique with small magic squares (6x6) and it works really fast. I haven't tried it yet with 9x9. One problem with this alternative technique is that it takes a lot of memory (a few Mb's for the 9! combinations in 9 arrays). I have yet to find out if it is quicker than my current method. In the meanwhile, what do you think?

Greets,

R

eclark · Posted: Sun Jan 08, 2006 11:11 am Post subject:

My guess is that dancing links or another implementation of depth first search will beat this pretty handily(especially if we look at 4x4 or 5x5) since it more intelligently guesses at correct positions. an Array of 9! is too large to truely hash with any speed in the way you are purposing. Though this would be a simpler way to generate smaller matrices. Though this is just a guess. Please let me know what you find out.

thehovenator · Posted: Sat Jan 03, 2009 9:25 am Post subject: THIS WORKS GREAT!!

I've been developing a Sudoku game using Java, and I successfully used this method to generate a sudoku. It is somewhat time consuming to generate every possible row combo (approx 3 minutes), but it only has to be done once, and you can generate as many as you want.
I personally love this method (since I was able to get it to work ). Smile