| rubylips
| | Joined: 07 Apr 2005 | | Posts: 62 | | : | | Location: London |
Items |
|
 Posted: Thu Apr 28, 2005 4:58 pm Post subject: Dancing Links |
 |
|
A recent posting by gcrhoads@yahoo.com on Su Doku to the rec.puzzles forum points out that it's possible to express a Su Doku puzzle as a special case of Knuth's 'Dancing Links' problem. (The following is very slightly edited):
| Quote: | > I translated the problem into an exact cover formulation and
> I've found some descriptions of the exact cover problem. Could you
> explain how you formulated Su Doku as such a problem?
The reason I used this problem is that Donald Knuth has a nice backtracking solver for this on his page http://www-cs-faculty.stanford.edu/~knuth/programs.html It's the one called DANCE for "dancing links." He has a nice paper about the "dancing links" technique on his page http://www-cs-faculty.stanford.edu/~knuth/preprints.html
In the exact cover problem, you are given a 0-1 matrix (all entries are either a 0 or a 1). The problem is to find a set of rows that collectively contain exactly one 1 in each column.
In my exact cover formulation of Su Doku, there are columns labeled xRy, xCy, xBy, xy for all integers x,y from 1 through 9. Each column corresponds to a constraint that must be satisfied exactly once. The following are examples of the meanings of these contraint labels.
2R3 -- means there must be exactly one 2 in Row 3
5C6 -- means there must be exactly one 5 in Column 6.
1B4 -- means there must be exactly one 1 in Block 4. The 3x3 squares are "blocks" and I numbered them 1 through 9 going left-to-right and top-to-bottom.
28 -- means there must be exactly one entry in the square at the intersections of row 2 and column 8.
(Row numbers increase going from top to bottom and column numbers increase going left to right.)
For each number and for each possible location, we have one row in our matrix with a 1 in exactly four columns. For example, the matrix row corresponding to placing a 4 in the fifth row and and seventh column has a 1 in the four columns labeled 4R5, 4C7, 4B6, and 57. (There are 729 total rows in the matrix. You can generate all this in the form required by Knuth's program with just a few small nested loops.)
Now it is easy to see how a solution to this exact cover problem corresponds to a solution to Su Doku (with no initial values provided). Every matrix row has a 1 in exactly one column of the form xy and for each such column, there must be exactly one row with a 1 in that column. Thus to satisfy the 81 contraints of the form xy, we must choose exactly 81 rows. In terms of Su Doku, this simply means that we must select exactly one number in each of the 81 locations on the board. In Su Doku, each digit must appear exactly once in each row, column, and 3x3 block. It should be clear that these contraints (and no other constraints) are enforced by other columns. In Su Doku, you are given the values of some subset of the locations. But this is easily handled. If you are given a 9 in row 6 column 2, then the row with a 1 in the columns 9R6, 9C2, 9B4, and 62 is one of your selected rows.
> From a list of the initial values, it takes only a short simple bit of code to pick out the initial rows that you require in the cover. So all told I needed only two small straightforward pieces of code in order to use Knuth's program.
> I'd considered trying to formulate the problem as a satisfiability
> problem just for kicks, but didn't have time to persue it.
You can get that directly from the 0-1 matrix in the above exact cover formulation. Have one boolean variable for each row of the matrix. For each column, make a boolean expression that is true if and only if, of all the variables that correspond to a row with a 1 in the column, exactly one of them is true. The overall formula is the conjunction of the column formulas. In Su DoKu, a given subset of values tells you which rows you want and hence, which variables must be fixed at true. |
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
