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   

Understanding DLX

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

Joined: 28 Mar 2006
Posts: 14
:

Items
PostPosted: Wed Apr 05, 2006 12:26 pm    Post subject: Understanding DLX Reply with quote

Ok, well I think I'm pretty much on my way to understanding how dlx works, but I wondered if anyone could just confirm my thoughts for me.

Ok:
1. use a matrix of 324x729
2. the rows of this matrix represent all possible placements (81 cells in a grid, 9 possible digits in each)
3. columns 4 groups of 81 for the four constraints of sudoku.
4. each row will have four 1s, one for each constraint when a number is input into a grid.

ok now my thoughts on solving
a. fill in the matrix with the 1s that correspond to the clue digits gioven
b. complete the matrix with the other remain poss moves
c. perform algorithm x

is this right??
Back to top
View user's profile Send private message
jdport

Joined: 19 Oct 2005
Posts: 13
:

Items
PostPosted: Wed Apr 05, 2006 3:45 pm    Post subject: Reply with quote

Ruud or one of the residential experts here can answer more completely than I am, but DLX is basically a streamlined version of Algorithm X. If you are actually creating an entire matrix and filling it with 1's and 0's and solving the matrix you are doing algorithm X but not DLX. DLX considers only the 1's, and ignores the 0's which is what makes it streamlined for sparse matricies.

So with DLX you have a double circular linked list with each node of the list being a "1" from the matrix. There are 729 rows, each row with 4 1's in it so you'll have 3,168 nodes total. You then eliminate the rows with the givens and make them part of your solution and solve the remaining "matrix" by manipulating the nodes of the linked list as described in Knuth's paper (which is basically doing Algorthm X).

I hope that a) this makes sense, and that b) i'm right ... i answered your question as much for my own benefit as for you because i'm still kind of learning this as well and hope that any corrections to what i just said will just enhance my own understanding while helping you at the same time Wink
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving 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