Beautiful Dancing Links
If you are going to walk on thin ice,
you may as well dance.
Dancing Links (DLX) is a technique suggested by Knuth for solving Exact Cover problem. Details are in the paper. Here I just give some outlines of DLX and how we can apply it to solve some types of searching problems.
The exact cover problem is to find a set of rows from a 0-1 matrix s.t. each column has exactly one 1. A common backtracking method is suggested by Knuth called the Algorithm X. Dancing links is a fast implementation of Algorithm X utilizing circular doubly linked links (hence the name DLX) taking the advantage that the more deeper we're at, the more sparse the current matrix is. It's fast in that it has fast updating/restoring of the backtracking context.
Searching problems are hard to solve. Though there are optimizations and pruning techniques available, they are very specific to the underlying problem -- usually we cant easily apply 'em across problems. Even for a specific problem, it's not easy to predict whether a heuristic really works (well). DLX can be used to solve a range of exact-cover-like problems and often it has reasonably good running time. All we need is to build the matrix model -- normally we use rows to denote states and columns conditions. And one optimization is that we always start searching the column that has the most 1s -- big first cut.
the classic exact cover problem. Just build the matrix and run the DLX. example: Sudoku. Each row is a (r,c,d) state denoting that we put digit d to position (r,c). Three types of the sudoku rules are mapped to some columns of the 01-matrix: each digit should appear once on each row, each column, and each 3x3 square. And also the condition that each position should be filled. You can try this method to solve a 16x16 sudoku.
loose cover problem: each column has at most one 1. Example: N-Queens Problem. The nqueens problem is in fact a mixture of exact cover and loose cover: every row and column has exactly one queen while every diagonal line has at most 1 queen. We can build and run the DLX as usual: only find the columns of 01-matrix that are corresponding to the row/column of the nqueen rules. Try solving this nqueens problem where some queens are already on board. [1]
repeated cover problem: each column has at least one 1. Example: minimum dominating set on a bipartite. We lose the row-exclusive-sweeping operation on a column due to the 'at least' rule. But we can augment the DLX a bit to justify this, and with a heuristic, it becomes an IDA*. The heuristic here is that at each recursion level, we find the minimal number of rows we have to get to meet the overall condition:
mark all uncovered column untaken ret = 0 for each untaken column: ret++ for each row having this column: mark every column on this row taken return ret
Here's a sample problem.
[1] Just note that you can also use the local search technique I mentioned in these blog entries -- when you go random, dont move those queens that are already on board.
