The exact cover problem is basically the following:
Given a grid of \(1\)s and \(0\)s, find a subset of the rows that contains exactly one \(1\) in each column. For example, given the grid:
0: 0 1 1 0 0 0 0 0 1
1: 1 1 0 1 1 1 1 1 0
2: 1 0 0 0 1 0 0 1 0
3: 0 0 0 1 0 1 1 0 0
4: 1 0 0 0 0 1 0 0 1
the solution is rows 0, 2, and 3.
The basic idea of dancing links is to represent the grid of \(1\)s and \(0\)s by creating a node data-structure for each \(1\) and giving each node four pointers (or links) to its neighbors to the left, right, above and below. Additional nodes called heads point to the first node in each column and to their head neighbors to the left and right. Finally there is a root node pointing to the first head. For example a structure that looks like:
| | |
- root - head - head - head -
| | |
- node - node - |
| | |
| | - node -
| | |
- node ----|--- node -none
| | |
- node -
|
would represent the grid:
1 1 0
0 0 1
1 0 1
0 1 0
The advantage of this representation is that temporarily removing a row from the list is a relatively cheap operation. All you need to do is visit each node in that row and connect its neighbors above and below to one another. To re-insert it, you simply reconnect the same above and below neighbors back to the node in the row. The linked structure is especially nice because size of the operation is related to the number of \(1\)s in the row as opposed to the length of the row. As we will see the grids for sudoku puzzles will have \(324\) columns but each row will only have four \(1\)s do this is a big win.
The algorithm itself is recursively defined by the following pseudo-code:
FUNCTION solve(grid) :
IF the grid has no columns (which is to say no heads)
this is a valid solution
RETURN TRUE
IF any of the heads points to nodes
there is no valid solution
RETURN FALSE
node = head.down
PICK any head and ITERATE through its nodes
assume that this node is in one of the rows of the solution
FIND the set of rows that the row this node is in conflicts with
(that is to say that contain a 1 in a column this contains a one in)
REMOVE those rows, as well as the one the current node is in, from the grid
self.removedRows.append(node.row) # Record row choic
CALL solve recursively on the smaller grid
IF the recursive call returns true this row is, in-fact a part of at least one solution
RETURN TRUE
ELSE
PUT BACK the removed rows
IF the loop completes without returning then there are none of the rows in the chosen column
can be a part of a solution and thus there is no solution
RETURN FALSE
Sudoku
So how does Sudoku map onto the exact cover problem? The answer is to notice that sudoku has four types of constraints of an "exactly one" nature:
- Each space must have exactly one number
- Each row must have exactly one of each number
- Each column must have exactly one of each number
- Each box must have exactly one of each number
There are \(81\) constraints of each type. Then notice that there are \(729\) possible moves in a sudoku puzzle, each of which satisfies one constraint of each type. To search for a solution to a blank sudoku puzzle you can simply generate a grid of \(1\)s and \(0\)s with \(324\) columns representing the constraints and \(729\) columns representing the possible moves then put a \(1\) in position for which that row's move satisfies that column's constraint. The solution to the exact cover problem for this grid represents a set of moves that can be made. To solve a sudoku problem with some numbers already filled in, simply make the moves that have already been made, that is to say, remove the rows corresponding to those nodes from the grid along with any rows that conflict with them and then solve the resulting smaller exact cover problem.
![[paper clip]](/courses/source/wiki_images/paper_clip_tilt.png)
name last modified size