COMPULSORY UPGRADE!!! Request an upgrade NOW! 32+ Pre-installed Modifications! 3 Server Locations to choose from: USA, UK and JAPAN.
11th December 2012 - setBB: All servers are upgraded to run using SSD drive. Click Here to report problems!
| View previous topic :: View next topic |
| Author |
Message |
| BryanL
| | Joined: 17 Jun 2010 | | Posts: 86 | | : | |
Items |
|
 Posted: Sun Aug 07, 2011 12:57 pm Post subject: |
 |
|
Hi blue,
thanks for all the explanations
| blue wrote: | | Quote: | | I have never tried it but i think it may be possible to also cover eliminated candidates. |
It did the thing that you mentioned: if some/any kind of testing reveals that a candidate can be eliminated, it can be removed from consideration by the DLX code, by unlinking the nodes in its (corresponding) DLX row, from thier respective columns.
To backtrack through something like that, you need code to link the nodes back into thier columns at the appropriate time, and bookkeeping code, to indicate when it's the "appropriate time", and which row to re-link.
For unlinking & re-linking, code similar to the innermost loop in the cover/uncover routines, will work.
Just be sure to handle every node in the row, instead of "all but one", like the cover/uncover code does. |
I had thought that covering row nodes would do the trick and was going to ask in the other thread.
I am only thinking of solving to a point and then calling dlx, never back and forth. So i assume that covering the relevant row nodes after covering the givens and then uncovering them before uncovering the givens would suffice without any other bookkeeping code?
| tarek wrote: | | Afmob wrote: | | You could only make it faster if you find a way to implement it with less additional columns and rows. Or you don't use DLX for intersections. |
Right then ... I'll try to think of something else then .....  |
Hopefully tarek, finding eliminations using normal methods, and applying those to the dlx matrix will give it a speed boost - how much? we will have to test...
| Quote: | On your comment about "large N", I agree, whole-heartedly.
Even (rare) 16x16 puzzles can run overnight, with no resolution, using stock DLX code. |
Ouch!
Thx again,
bryan
.
|
|
| Back to top |
|
 |
| blue
| | Joined: 12 May 2010 | | Posts: 318 | | : | |
Items |
|
| Posted: Sun Aug 07, 2011 3:56 pm Post subject: |
|
|
Hi Bryan,
| Quote: | | I am only thinking of solving to a point and then calling dlx, never back and forth. So i assume that covering the relevant row nodes after covering the givens and then uncovering them before uncovering the givens would suffice without any other bookkeeping code? |
You'ld need to re-link the rows, in the reverse unlink order.
As long as you can do that, you're fine.
Regards,
Blue. |
|
| 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 |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
