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

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

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Thu Apr 28, 2005 4:58 pm    Post subject: Dancing Links Reply with quote

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.
Back to top
View user's profile Send private message Visit poster's website
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