|
View previous topic :: View next topic |
Author |
Message |
| s0nny_black
| Joined: 28 Mar 2006 | Posts: 14 | : | | Items |
|
Posted: Wed Apr 05, 2006 12:26 pm Post subject: Understanding DLX |
|
|
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 |
|
|
| jdport
| Joined: 19 Oct 2005 | Posts: 13 | : | | Items |
|
Posted: Wed Apr 05, 2006 3:45 pm Post subject: |
|
|
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 |
|
Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|