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

FlukeLogic

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

PIsaacson · Posted: Tue Feb 23, 2010 3:02 am Post subject:

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

FlukeLogic · Posted: Tue Feb 23, 2010 3:39 am Post subject:

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):

PIsaacson · Posted: Tue Feb 23, 2010 6:00 am Post subject:

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