Dancing Links 跳舞链

Dancing Links缩写为DLX，其实在竞赛中并不常见，这次会讲这个是因为前一阵子搞拼图写了这个数据结构就顺便写(水)博客。

DLX的发明者是高德纳（Donald Knuth），就是那个传说中的《计算机程序设计艺术》（TAOCP）系列书的作者，这里对这个算法做一些比较直观的解释。

DLX面向的问题

DLX面向的问题是精确覆盖问题。何谓精确覆盖呢，来看以下这个表格，每一行是一个数组，数组有4个元素，每行的第一列是这个数组的名字

我们的目标是，在这些集合里，挑出几个，例如我们挑a,b,c，那对应位置上的元素相加，于是得到 2 1 0 2。而我们的目标是，找到一个挑选的方法，使得相加得到 1 1 1 1 全是1。

例如说，选 d和g，那么相加正好得到 1 1 1 1 ，这就是其中一个解，这就是精确覆盖问题的直观感知。

朴素算法的构思

我们来一把朴素DFS，例如说，先选择了集合a，而集合a在第4列是个1，那么，其它在第4列同样是1的集合之后就不用再看了，把这些行统统删除，在剩下的行中再选取一行，如此递归进行。我们会发现，怎么选取那一行，以及怎么样高效删除和恢复列，对这个搜索过程的效率有着关键性的影响。

DLX的数据结构

在学习稀疏矩阵的时候，我们有一个表示稀疏矩阵的数据结构，就是十字链表，十字链表的优点是可以快速删除一行或一列。DLX就是使用十字链表表示这个矩阵。然后就是行的选取方式上，随便选一行目标性不佳。你如果玩过数独，那你可能会感觉这有点像数独，如果某一列，只有一个1，那么对应的含1的行，就确定一定是它了。而如果没有这种情况，我们就去找某一列只有两个1的。换句话来说，我们会从某一列中，含有最少的1的个数的列，来选择含有1的行。

为了能快速知道某一列的1的数量，那必须增加一个头部记录这个信息。再者，某些列删除后，我们也需要快速找到还没有删除的列，所以之前的表格可以换成以下的表示：

其中，head那一行包含在十字链表内，但不参与覆盖计算，仅用于索引还没有删除的列。而size是一个数组，不在十字链表内。所以列有表头，但行没有，head行是双向链表不循环，末尾元素的right指向空，其它的每一行是一个双向循环链表，而列是双向链表不循环，最底下的元素的down指向空。当然以上你也可以全做成循环的链表，稍微调整一下循环的结束条件即可。

DLX的删除与恢复

通常，在链表里如果删除一个元素，那么被删的元素的指针要改为指向空。但是，在DLX里面不需要改，不改的好处就是能够用这个指针进行恢复操作。我们用双向链表来模拟一下删除和恢复的过程，以下是5个元素的初始状态

graph LR;
linkStyle default interpolate basis
0-->1
1-->0
1-->2
2-->3
3-->4
4-->5
2-->1
3-->2
4-->3
5-->4

删除节点2

graph LR;
linkStyle default interpolate basis
subgraph main
0-->1
1-->0
1-->3
3-->4
4-->5
3-->1
4-->3
5-->4
end
subgraph deleted
2-->3
2-->1
end

删除节点3

graph LR;
linkStyle default interpolate basis
subgraph main
0-->1
1-->0
1-->4
4-->5
4-->1
5-->4
end
subgraph deleted
2-->3
2-->1
3-->4
3-->1
end

删除节点4

graph LR;
linkStyle default interpolate basis
subgraph main
0-->1
1-->0
1-->5
5-->1
end
subgraph deleted
2-->3
2-->1
3-->4
3-->1
4-->5
4-->1
end

然后，要恢复的时候，如果先恢复节点4，再恢复3，最后2，那么就正好得到上图的逆序，就不重复展示了。但是如果，我们先恢复2，再是4，最后3，那会发生什么呢？来看看如果先恢复2，恢复就是让这个节点原本两端指针指向的元素重新指向自己，于是得到下图

graph LR;
linkStyle default interpolate basis
subgraph main
0-->1
1-->0
1-->2
5-->1
end
subgraph deleted
2-->3
2-->1

3-->4
3-->2
4-->5
4-->1
end

有点怪怪的，先不管，再恢复4

graph LR;
linkStyle default interpolate basis
subgraph main
0-->1
1-->0
1-->4
5-->4
2-->1
end
subgraph deleted
2-->3

3-->4
3-->2
4-->5
4-->1
end

最后恢复3

graph LR;
linkStyle default interpolate basis
subgraph main
0-->1
1-->0
5-->4
2-->1
end
subgraph z
2-.->3

3-->4
3-->2
4-->5
4-->3
1-->4
end

结果2到3这条边多赋值了一次，这里用虚线表示。但这不重要，重要的是链表数据结构已经错了，从1指向4这条边没有恢复成1指向2。所以，这里有个很简单的原则，恢复的时候要完全逆序，千万不能打乱顺序。

DLX具体应用之拼图

所谓的精确覆盖其实是一类问题，具体问题有像8皇后问题，伤脑筋13块，智慧珠游戏，数独游戏都是典型的精确覆盖问题。为了方便说明，我们简化成以下问题：

有一块1x2和2x2的方块，怎么拼成一个3x2的矩形

这个怎么用DLX来解呢，首先我们要先对这个3x2的矩形编号：

然后，给1x2这个方块编号7，2x2这个方块编号8，所以我们有8列。然后穷举每个块可以摆放的位置，每一种情况就作为一行，那位置覆盖的矩形编号就对应十字链表中的列：

前7行就是1x2这个块的所有情况，8和9行就是2x2这个块的所有情况。

表格做出来了，解法也很简单，看，第8列1的个数最少，那先选第8行，然后删除第8行上是1的所有列，然后只剩下第7行，于是找到第一个解{7,8}。然后第8列如果选另一行，即第9行，然后删除第9行上是1的所有列，然后只剩下第5行，于是找到第二个解{5,9}。于是所有解就都找到了。

DLX应用之n皇后问题

在棋盘上任意位置放一个皇后，相当于同时覆盖了棋盘这一行、这一列、相应的/斜线、相应的\斜线。而n*n的棋盘，有n行n列和2n-1条斜线，所以做成表格将有6n-2列，n^2行，每行恰有4个1。具体表示这里不写了，因为页面宽度不够。

DLX应用之数独问题

和n皇后问题类似，考虑在某个格子写了一个数k，那么相当于同时覆盖了这一行的数字k，列数字k，这个3x3区域的数字k，所以表格列数是9*9*3，表格行数是9*9*9，每一行都恰有3个1。初始化这个表格后，数独问题本身有一些初始数字，我们就根据这些数字，找到它所属的行，把这些行有1的列统统删掉，再执行搜索即可。

DLX的剪枝

剪枝有两类，一种是看实际问题需求产生的剪枝，另一类是与具体问题无关可以在DLX上通用的剪枝。

通用剪枝

假如不存在某一行全是1（99.9%的问题都不应该有吧），那这个剪枝就可以使用。在开始DFS搜索之前，我们如果先选定一行，然后把它有1的列删除，然后看有没有列的1的数量为0，如果有，那么这一行一定不可能在解里面，那么就可以把这一行从链表里直接删除干净，这样直到没有这样的无效行再去启动搜索即可。这个剪枝对于规模更大的问题求所有解时，加速效果明显。

特定问题的剪枝

对于正方形拼图，有个很明显的点，就是当你随便发现一个解时，那它翻转、旋转便会得到另外7个解，我们希望可以去掉这些镜像解，只保留本质不同的解。那么，我们可以记录四角的编号，例如矩形是3*3时，它的编号就是1,3,7,9，另外再增加一个字段，记录覆盖这一列的时候是选取的哪一行。这样当我们在搜索的过程中覆盖到这些列的时候，就可以启动单调性剪枝，我们定义1号用的行最小，3号比7号要小，如果与定义的不同，那就可以直接return，这样不但搜索时间减少不少，而且得到本质解的数量，一举两得。对于非正方形的矩形，或其它对称形状也有类似方法，可以去掉至少一半的重复解。

原始DLX算法的局限

原始DLX算法最害怕的东西有两个，一是有大量的行极相似，二是有大量的行上面1的数量太少（<=2），这对应于具体问题是什么情况呢，例如说我之前博文的Orz14拼图，它不是精确覆盖，但可以转为精确覆盖问题，只需要补上17个1x1方块即可，但是这样的话，DLX的搜索时间是完全不可接受的，这个拼图同时满足了前面的两个条件，因为有大量的块形状完全一样，那么生成的行每行都有另外13行与之极相似，会导致相同的覆盖方式重复搜索，重复量级约 $14!$ ，好像不是特别多，其实要这么想，如果去重复后计算时间要1秒，那不去重复就需要 $14! = 87178291200$ 秒或者说2700多年。另外由于要补上的1x1方块非常多，而这些1x1方块在每一行只有2个1，同样也产生了 $17!$ 的重复，所以原始算法不适合解决这种问题，必须对其进行改进，或更换其它搜索方式。