Sudoku Programmers Forum Index

 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Your opinion on this method for generating a full grid?

Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message

Joined: 07 Jan 2006
Posts: 1

PostPosted: Sat Jan 07, 2006 6:48 pm    Post subject: Your opinion on this method for generating a full grid? Reply with quote


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?


Back to top
View user's profile Send private message

Joined: 28 Dec 2005
Posts: 70

PostPosted: Sun Jan 08, 2006 11:11 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message

Joined: 03 Jan 2009
Posts: 1
Location: Utah

PostPosted: Sat Jan 03, 2009 9:25 am    Post subject: THIS WORKS GREAT!! Reply with quote

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
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Page 1 of 1

Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 

Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron