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   

Random grids with DLX

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

Joined: 12 Oct 2006
Posts: 6
:
Location: Liverpool L8

Items
PostPosted: Thu Oct 12, 2006 5:05 pm    Post subject: Random grids with DLX Reply with quote

I use DLX to generate and solve Sudokus.

To generate them, I start off with a completely blank grid.

To select a column, the program collects all the columns with the smallest size and chooses one at random (so for the first pass, this could be any of the 324 columns, all with size 9).

My question is - am I restricting the randomness of the grid in anyway, as the first step will always choose the first row in any column? If I left it to run and run, would it (theoretically) generate every single Sudoku solution?

Perhaps, I would be better as a first step to pick a row at random and cover those columns before moving into the dance? What do you think?
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Oct 12, 2006 6:53 pm    Post subject: Reply with quote

When you always select the first node in the selected column, your method will certainly be biased. But even when you pick a random node, your method will probably create clusters of given numbers around your first placement.

I use a similar method to create a solution grid (by assigning random numbers to the columns before DLX starts), and then clear random values from this grid until it is fully (or symmetrically) minimal.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
brassbandit

Joined: 12 Oct 2006
Posts: 6
:
Location: Liverpool L8

Items
PostPosted: Thu Oct 12, 2006 8:11 pm    Post subject: Reply with quote

I like the idea of the random number with each column.

Presumably that means there are large variances in time taken to find a solution - you might select a column at random with six nodes still attached and may have to go through each of these until a solution is found? That's an extreme case, of course, it could be that a solution is found with no backtracking at all required.

Does your method start at a random row in the column and try them all in turn (until a solution is found)?

Sounds like your method is similar to mine for removing numbers - I randomize the numbers 0 to 80 (or 40 for symmetry) and remove each clue(s) in turn, replacing it if it fails to give a unique solution.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Oct 12, 2006 9:30 pm    Post subject: Reply with quote

brassbandit wrote:
Presumably that means there are large variances in time taken to find a solution.

Not really. My answer was not complete. To ensure complete randomness, I also assign a random number to each row before I link them to the headers. When the random number is less than that of the last node attached to the header (including the column header itself), the new node will be inserted before the header, otherwise after the header. This means that I can simply pick the first node below each header when dancing towards a solution. The little time needed for this extra initialization is well spent, considering the complex algorithms required to pick a random node from a column.
Back to top
View user's profile Send private message Visit poster's website
brassbandit

Joined: 12 Oct 2006
Posts: 6
:
Location: Liverpool L8

Items
PostPosted: Fri Oct 13, 2006 6:49 am    Post subject: Reply with quote

Ah, I see what you're doing now. That's great, and guarantees complete randomness. Thanks.
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