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   

C++ Sudoku Solver Using DLX - Which Rows = Solution?

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

Joined: 17 Nov 2008
Posts: 8
:

Items
PostPosted: Sun Feb 21, 2010 8:29 pm    Post subject: C++ Sudoku Solver Using DLX - Which Rows = Solution? Reply with quote

Hello all,

Using DLX, the way we know the puzzle is solved is because Root->Right = Root (indicating that all columns have been covered).

What I don't understand is how, during the DLX covering/uncovering operations, the rows that meet the constraints are "remembered."

In other words, when the algorithm has covered all columns, how do we know all the subsets whose union gives us the exact coverage we've been looking for?

It's more confusing yet when I see that the root node of the header row has no up/down pointers. So if Root->Up and Root->Down don't point to anything, so how can we know the rows that brought us to this end result?

I've been through the code of 3 different solvers that use DLX - one in C#, one in C++ and one in Pascal, but I just can't see how they're doing it. It simply prints solution but I don't see where it was storing that solution.

If anyone can throw me in right direction (keep in mind I'm a new C++ programmer) I would appreciate it.

Thanks!

EDIT::trimmed the post - made title more specific
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Feb 23, 2010 3:02 am    Post subject: Reply with quote

In all of the various DLX implementations that I have seen, there is a solution stack/array that contains the rows under consideration. Associated with this stack/array is some level/depth variable that indicates which element of the stack contains the current row being processed. This variable is incremented after a row is selected, covered and placed on the solution stack, and then decremented before the row is uncovered. If a solution is found for a sudoku exact cover problem, then the stack will contain the exact 81 out of the 729 possibles that satisfy all 324 constraints.

Review the code and algorithm at http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/

You can see the above implemented as Result (stack) and nResult (variable) in the Search function. The PrintSolution function uses the Result stack and nResult variable to print the discovered solution.

Cheers,
Paul
Back to top
View user's profile Send private message
FlukeLogic

Joined: 17 Nov 2008
Posts: 8
:

Items
PostPosted: Tue Feb 23, 2010 3:39 am    Post subject: Reply with quote

Aha! This is one of the solvers I looked at. I didn't see it until you pointed it out though. So this (correct me if I'm wrong):

Code:

Result[nResult++] = RowNode->IDNum;


Is where they are storing the result. Then when they print the solution it's using that weird 3 digit index to determine the row/column and value. Is that really necessary/productive, in your experience?
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Feb 23, 2010 6:00 am    Post subject: Reply with quote

The "weird 3 digit index" is the nrc representation of the 3d space defined by number/row/column coordinates. Since each dimension contains the value range 1-9, this defines the 9x9x9 or 729 candidate space of a sudoku puzzle. The 324 constraints mandate that each row/col/box/cell must uniquely contain all the digits 1-9, so 4x9x9 or 324 total constraints. Understanding the basis of these numbers and how they absolutely relate to a sudoku puzzle and the solution is fundamental for programming an effective sudoku solver.

This should lead you to the inference that many sudoku techniques can be implemented by the use of various logical formulas and multiple 729, 324 and 81 long bitmaps. I highly recommend studying the STL (Standard Template Library) bitset template and functions (Google is your friend) for implementing highly efficient bitmap operations for these in C++.

Clearly there are multiple design decisions to make regarding your core grid object. As you implement additional techniques, you will probably discover that you need additional supporting data structures. But before you proceed too far, I highly recommend searching this forum and the Sudoku Players Forum for both algorithms and coding examples. There are many years of experience here waiting for you to explore.

Cheers,
Paul
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