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   

Dancing Links Matrix

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

Joined: 02 Nov 2005
Posts: 7
:

Items
PostPosted: Wed Nov 02, 2005 7:42 pm    Post subject: Dancing Links Matrix Reply with quote

I'm having trouble working out how to map a given sudoku puzzle to a binary matrix as describe in the Addendum of this document

http://spivey.oriel.ox.ac.uk/mike/comp2005/results.html

Could someone please post either some pseudocode or the top left corner of a binary matrix with puzzle so that I can see an example.

All help appreciated.
Back to top
View user's profile Send private message
barcode

Joined: 02 Nov 2005
Posts: 7
:

Items
PostPosted: Thu Nov 03, 2005 7:05 pm    Post subject: Reply with quote

Nobody? Sad
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Nov 04, 2005 1:08 am    Post subject: Reply with quote

http://magictour.free.fr/suexco.txt
Back to top
View user's profile Send private message Send e-mail Visit poster's website
barcode

Joined: 02 Nov 2005
Posts: 7
:

Items
PostPosted: Fri Nov 04, 2005 3:13 pm    Post subject: Reply with quote

Thanks, hopefully this will give me the mental nudge I need to 'get it'.

Andy
Back to top
View user's profile Send private message
barcode

Joined: 02 Nov 2005
Posts: 7
:

Items
PostPosted: Fri Nov 04, 2005 3:42 pm    Post subject: Reply with quote

Right, having looked at the code, it seems that I'm populating my initial matrix right (so the binary matrix that represents the generic constraints of Sudoku), but I'm unsure how to add the contraints represented by a puzzles givens.

My first guess was to not add the rows for possibilities we know cannot be true due to a give. So if we know there is a 1 in row 1 cell 1 then we wouldn't add the 8 rows representing other numbers within the cell. However that doesn't seem to work.

Your code if I'm reading it right has two arrays Ur and Uc which specify rows that cannot be in the solution and eliminates them during the main run.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Nov 04, 2005 3:56 pm    Post subject: Reply with quote

yes, it should work.
You might also remove the deleted rows from the adressing
by the columns.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
barcode

Joined: 02 Nov 2005
Posts: 7
:

Items
PostPosted: Fri Nov 04, 2005 4:49 pm    Post subject: Reply with quote

Yes, I was right all alone, I had accidentally typed an i instead of a j in my code which threw everything out. So it all works now. Highly un-optimised at the moment and the code is a mess but it runs in 80millis which isn't too bad.

Do you mean I should 'cover' the columns?
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming 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