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   

How to rerun DLX algorithm on the same matrix?

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

Joined: 05 Jun 2006
Posts: 7
:

Items
PostPosted: Fri Jun 09, 2006 4:52 pm    Post subject: How to rerun DLX algorithm on the same matrix? Reply with quote

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
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Jun 09, 2006 7:15 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
veroslav

Joined: 05 Jun 2006
Posts: 7
:

Items
PostPosted: Fri Jun 09, 2006 8:00 pm    Post subject: Reply with quote

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 Smile but I will have to give it another look or two and go with the old System.out for a couple of days. Wink I'll hear from me if I succed. Thanx again.

Regards,
Veroslav
Back to top
View user's profile Send private message
veroslav

Joined: 05 Jun 2006
Posts: 7
:

Items
PostPosted: Mon Jun 12, 2006 5:42 pm    Post subject: Reply with quote

I am back, I debugged the program for a whole weekend and no success Sad 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! Sad 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? Sad Please, help

Regards,
veroslav
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