Dancing Links
One of my co-workers forwarded me a copy of Dancing Links by Donald Knuth. In the paper, Knuth describes a backtracking algorithm, DLX, for solving exact cover problems using a doubly-linked-list type data structure. As the algorithm recursively searches for possible solutions, the links in the lists that represent the problem "dance" as they are updated from previous candidate solutions to reflect the candidate solution that is currently under consideration.
What is the exact cover problem? Given a set of elements U and a collection S of subsets of U, an exact cover C of U is a subset of S so that each element of U appears in exactly one of the subsets in C.
For example, suppose U = { 1, 2, 3, 4, 5 } and S = { S1 = ( 1, 5 ), S2 = ( 1, 2, 4 ), S3 = ( 2, 3, 5 ), S4 = ( 2, 4 ), S5 = ( 1, 4 ), S6 = ( 3 ), S7 = ( 4 ) }. Then an exact cover of U is { S1, S4, S6 } since together these three sets have all of the elements U = { 1, 2, 3, 4, 5 } and no elements appears in more than one of S1, S4, S6. Similarly, { S3, S5 } is another exact cover. On the other hand, { S1, S3, S7 } is not an exact cover because 3 appears in both S1 and S3. Likewise, { S2, S6 } is not an exact cover because neither S2 nor S6 contains 5.
Suppose you are given a chessboard (an 8 x 8 grid) and 32 dominos (2 x 1 rectangles), which have squares of the same size as the chessboard. Can you place the dominos on the chessboard so that each square of the chessboard is cover? Yes; and it should be straightforward to do! (e.g. Make a row of four dominos that are horizontal. That will cover one of the ranks of the chessboard. Simply repeat this seven more times). Now, what happens if I give you 31 dominos and cut away the top left (a8) and bottom right (h1) squares of the chessboard (so it has 30 white and 32 black squares). Can you cover this modified chessboard with your 31 dominos?
If the domino and chessboard example still sounds too contrived then consider how you would write a computer program that can solve Su Doku problems. [Hint: Dancing Links!]
No comments:
Post a Comment