|
View previous topic :: View next topic |
Author |
Message |
| veroslav
| Joined: 05 Jun 2006 | Posts: 7 | : | | Items |
|
Posted: Fri Jun 09, 2006 4:52 pm Post subject: How to rerun DLX algorithm on the same matrix? |
|
|
Hi all,
I have implemented DLX algorithm and it works fine. The only problem that I have is that it works only once. If I run the algorithm for a new puzzle but on the same matrix, the only thing I get is a lot of errors. I have to reinitialize the matrix for every new puzzle. I would like to use the same matrix for every puzzle and only make necessary changes in it so that it works for the next problem as well.
I assume it has to do something with linking of the rows/columns, as they are linked/unlinked during the search step of the algorithm. I need some help to figure out what should be done so that the matrix becomes the same as before running the algorithm.
Any help is welcomed, as I have been stucked here for days without being able to figure out how it should be done.
Regards,
Veroslav |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Fri Jun 09, 2006 7:15 pm Post subject: |
|
|
If DLX works fine in a single run, then the linking-unlinking seems to work OK.
It could be that you're not correctly reversing the rows disabled because of the given digits. That too should be done in reverse order.
You can always add a little redundant data under a compiler directive to see where the differences are before & after a run.
Ruud. |
|
Back to top |
|
|
| veroslav
| Joined: 05 Jun 2006 | Posts: 7 | : | | Items |
|
Posted: Fri Jun 09, 2006 8:00 pm Post subject: |
|
|
Thank you for a reply Ruud. That was exactly what I thought too, the part where I enable the rows again when DLX is done. Its just that I'we been checking the code that does this hundreds of times and it SEEMS fine but I will have to give it another look or two and go with the old System.out for a couple of days. I'll hear from me if I succed. Thanx again.
Regards,
Veroslav |
|
Back to top |
|
|
| veroslav
| Joined: 05 Jun 2006 | Posts: 7 | : | | Items |
|
Posted: Mon Jun 12, 2006 5:42 pm Post subject: |
|
|
I am back, I debugged the program for a whole weekend and no success I tried the following:
I solved two puzzles, both with re-creation of the matrix and with the same matrix. I also added System.outs that print the whole matrix: all the nodes (they have unique indexes), each link for each node (left, right, lower, upper, column header), master header, size of each column header. I printed those for both cases at following places:
before removing givens (disabling the rows), after removing givens, before search, after search, after enabling the rows...guess what? the matrices are IDENTICAL at all those places in both cases! The ONLY difference I found was in chooseColumn method: during the case with the same matrix and during the solving of the other puzzle, there was difference between selected columns in two cases:
with the same matrix, it choose digit = 2 in box = 9 and size of this column was 0, with the new matrix, it choose digit = 2 at row = 6 and column size = 1. The later is correct, because there is a 2 at r9c9 so the former column should not have been there at all! But when I checked the matrices before search they were same as I said...This causes backtracking and ultimately leads to the wrong solution, that there is no solution.
Now, I am really frustrated and any help will be, once again, highly appreciated, as I am stuck now. What should I check now? maybe better to write the whole program from beginning? Please, help
Regards,
veroslav |
|
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
|