动手实现Dancing Links

前几天提到舞蹈链算法，这两天有时间就动手实现了一下。

舞蹈链（Dancing links）实际上是一种数据结构，可以用来实现 X算法，以解决精确覆盖问题。

什么是精确覆盖（Exact Cover）问题呢？维基百科上对精确覆盖的定义如下：在一个全集 X 中若干子集的集合为 S。S* 是 S 的一个子集，当且仅当 X 中的每一个元素在 S* 中恰好出现一次时，S* 称之为一个精确覆盖。在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个NP-完全问题。

例如，S = {A，B，C，D，E，F} 是全集 X = {1，2，3，4，5，6，7} 的一个子集的集合，其中：
A = {1, 4, 7}
B = {1, 4}
C = {4, 5, 7}
D = {3, 5, 6}
E = {2, 3, 6, 7}
F = {2, 7}
那么，S 的一个子集 S* = {B, D, F} 是 X 的一个精确覆盖，因为 X 中的每个元素恰好在 S* 中出现了一次。

可以用 0-1 矩阵来表示精确覆盖问题。我们用矩阵的每行表示 S 的一个元素，也就是 X 的一个子集；用矩阵的每列表示 X 的一个元素。矩阵中的 1 代表这一列的元素存在于这一行对应的子集中，0 代表不存在。那么精确覆盖问题可以转化成求出矩阵若干行的集合，使得集合中的每一列恰好都有一个 1。

比如前面的问题可以用矩阵的形式表示成

$\begin{array} {c|ccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline A & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \color{#d00}{B} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{0} \\ C & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \color{#d00}{D} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{1} & \color{#d00}{0} \\ E & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ \color{#d00}{F} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{1} \end{array}$

那么选择红色的 B，D，F 能满足每列都恰好包含一个 1。

可以用 Knuth 提出的 X算法来解决精确覆盖问题。X算法是一个非确定性的深度优先回溯算法。它的具体步骤如下：

如果矩阵 $A$ 为空（没有任何列），则当前局部解即为问题的一个解，返回成功；否则继续。
根据一定方法选择第 c 列。如果某一列中没有 1，则返回失败，并去除当前局部解中最新加入的行。
选择第 r 行，使得 $A_{r, c}$ = 1（该步是非确定性的）。
将第 r 行加入当前局部解中。
对于满足 $A_{r, j}$ = 1的每一列j，从矩阵 $A$ 中删除所有满足 $A_{i, j}$ = 1的行，最后再删除第 j 列。
对所得比 A 小的新矩阵递归地执行此算法。

让我们用 X算法解决上面的精确覆盖问题。

首先，当前矩阵不为空，算法继续进行。那么先选择 1 最少的一列。因为 1，2，3，5，6 列都只有 2 个 1，因此我们随便选择 1 个，比如第 1 列。

$\begin{array}{c|ccccccc} & \color{#d00}{1} & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline A & \color{#d00}{1} & 0 & 0 & 1 & 0 & 0 & 1 \\ B & \color{#d00}{1} & 0 & 0 & 1 & 0 & 0 & 0 \\ C & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ D & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ E & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ F & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{array}$

行 A 和 B 都含有 1，因此要在这两行中进行选择。

先尝试选择行 A。将行 A 加入到当前的解中。
$\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & \color{#AD3}{7} \\ \hline \color{#d00}{A} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} \\ B & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ C & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ D & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ E & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ F & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{array}$
行 A 的 1，4，7 列为 1，根据第 5 步，需要把所有在 1，4，7 列中含有 1 的行都删除掉，因此需要删除掉行 A，B，C，E，F，同时删除掉第 1，4，7 列
$\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & \color{#AD3}{7} \\ \hline \color{#AD3}{A} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} \\ \color{#AD3}{B} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & 0 \\ \color{#AD3}{C} & 0 & 0 & 0 & \color{#d00}{1} & 1 & 0 & \color{#d00}{1} \\ D & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ \color{#AD3}{E} & 0 & 1 & 1 & 0 & 0 & 1 & \color{#d00}{1} \\ \color{#AD3}{F} & 0 & 1 & 0 & 0 & 0 & 0 & \color{#d00}{1} \end{array}$
删除之后，矩阵只剩下行 D 和第 2，3，5，6 列：
$\begin{array}{c|cccc} & 2 & 3 & 5 & 6 \\ \hline D & 0 & 1 & 1 & 1 \\ \end{array}$
进入递归，回到第 1 步，矩阵非空，算法继续执行。
再进入第2步，此时选择 1 最少的第 2 列，里面没有 1，因此返回失败，同时将行 A 从当前的解中移除；

算法进入另一个分支，选择行 B，并将其加入到当前的解中：
$\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & 7 \\ \hline A & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \color{#d00}{B} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & 0 \\ C & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ D & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ E & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ F & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{array}$
行 B 的第 1，4 列为 1，因此要把 1，4 列中包含 1 的行都删掉。需要删除掉行 A，B，C，再删除掉 1，4 列。
$\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & 7 \\ \hline \color{#AD3}{A} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & 1 \\ \color{#AD3}{B} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & 0 \\ \color{#AD3}{C} & 0 & 0 & 0 & \color{#d00}{1} & 1 & 0 & 1 \\ D & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ E & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ F & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{array}$
此时矩阵变为
$\begin{array}{c|ccccc} & 2 & 3 & 5 & 6 & 7 \\ \hline D & 0 & 1 & 1 & 1 & 0 \\ E & 1 & 1 & 0 & 1 & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}$
进入递归，回到第 1 步，矩阵非空，因此算法继续。
当前包含 1 最少的一列是第 5 列，那么将从第 5 列中选择含有 1 的行进行搜索。
$\begin{array}{c|ccccc} \ & 2 & 3 & \color{#d00}{5} & 6 & 7 \\ \hline D & 0 & 1 & \color{#d00}{1} & 1 & 0 \\ E & 1 & 1 & 0 & 1 & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}$

第 5 列中行 D 含有 1，因此选择行 D，将其加入当前解中，算法进入新的一层搜索。
$\begin{array}{c|ccccc} & 2 & \color{#AD3}{3} & \color{#AD3}{5} &\color{#AD3}{6} & 7 \\ \hline \color{#d00}{D} & 0 & \color{#d00}{1} & \color{#d00}{1} & \color{#d00}{1} & 0 \\ E & 1 & 1 & 0 & 1 & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}$
行 D 的第 3，5，6 列包含 1，我们要删掉这几列中包含 1 的所有行，同时删掉这几列
$\begin{array} {c|ccccc} & 2 & \color{#AD3}{3} & \color{#AD3}{5} &\color{#AD3}{6} & 7 \\ \hline \color{#AD3}{D} & 0 & \color{#d00}{1} & \color{#d00}{1} & \color{#d00}{1} & 0 \\ \color{#AD3}{E} & 1 & \color{#d00}{1} & 0 & \color{#d00}{1} & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}$
那么我们需要删掉行 D，E 和第 3，5，6 列，矩阵变为
$\begin {array}{c|cc} & 2 & 7 \\ \hline F & 1 & 1 \end{array}$
再次递归执行，回到第 1 步，矩阵非空，因此算法继续
选择当前包含 1 最少的一列，这里选择第 2 列。第 2 列中只有行 F 包含 1，因此选择行 F

将行 F 加入到当前解中，算法进入第 3 层搜索
$\begin{array} {c|cc} & 2 & 7 \\ \hline \color{#d00}{F} & \color{#d00}{1} & \color{#d00}{1} \end{array}$
行 F 中第 2，7列为 1，第 2，7 列中行 F 包含 1，因此移除行 F 和第 2，7 列
$\begin{array} {c|cc} & \color{#AD3}{2} & \color{#AD3}{7} \\ \hline \color{#AD3}{F} & \color{#d00}{1} & \color{#d00}{1} \end{array}$
算法再次进入递归执行，回到第 1 步，此时所有的列都被移除了，矩阵为空，因此返回成功，找到了一个解：{B, D, F}

继续搜索，没有其他可以选择的行，返回上一层；

第 2 层也没有其他可以选择的行，再返回上一层；

第 1 层也没有其他可以选择的行，再返回上一层；

第 0 层也没有其他可以选择的行，算法终止。

以上就是 X 算法的执行过程。Knuth 提出 X 算法主要是为了说明舞蹈链的作用，他发现用舞蹈链来执行 X 算法效率特别高。那么什么是舞蹈链呢？它是基于双向链表的一种数据结构。

让我们先来看看双向链表：

Doubly linked list

上图是一个简单的双向链表，每个节点有两个指针，分别指向自己的前驱和后继节点。那么如果我们想把其中一个节点，比如 B 从链表中删掉，只需要执行下面的操作：

B.left.right = B.right
B.right.left = B.left

注意：此时虽然 B 从链表中移除了，但它的两个指针依然保持不变，还是指向之前的前驱和后继节点。

B is removed

因此，如果我想把 B 再添加到链表原来的位置上，此时并不需要修改 B 的指针，只需要再把 B 的前驱和后继节点的指针恢复就可以了：

B.left.right = B
B.right.left = B

理解了这一点之后，让我们再来看看舞蹈链的结构是怎么样的：

Dancing links

上面这个图是一个舞蹈链的结构，描述的是前面 X 算法中用到的矩阵。它由几部分构成：

最上面的蓝色部分是一个水平的环状双向链表。最左边是头节点，它是整个数据结构的根节点。其余是列头节点，每个代表矩阵中的一列。

每一列又是一个纵向的环状双向链表。除了最上面的列头节点，其他的每个节点都代表前面的矩阵中的一个 1。这实际上是一个稀疏矩阵，为了优化存储和效率，只保留了值为 1 的节点，把每个节点按顺序保存到数组中。最早的 Dancing Links 算法，也就是 Knuth 在 2000 年发表的论文中，下面的每一行也都是一个双向链表。但后来他发现每一行在算法执行过程中实际上不会发生变化，因此他把水平的双向链表取消了，只保留了最顶上的列头节点之间的水平双向链表。下面的每一行之间的前后节点可以直接通过数组的索引得到。两边是Space节点，用来标记一行的开始和结束。

每个普通节点 A 都包含 4 个字段，A.up 和 A.down 代表双向链表的两个指针，分别指向 A 上面和下面的节点。还有一个 A.col ，指向 A 所在列的头节点，需要根据这个字段定位到节点所在的列。另外还有一个 A.row，主要是方便在递归的过程中缓存当前的解。

列头节点还要再多几个字段，left 和 right 分别指向水平双向链表的左节点和右节点。另外还有一个 count 字段，代表这一列当前一共有几个元素。X 算法的第 2 步，选择 1 最少的列时会用到这个字段。

理解了舞蹈链的数据结构之后，我们再来看看是怎样用舞蹈链来实现 X 算法的。这部分算法很精妙，也是舞蹈链这个名字的来由，通过对链表上的节点反复删除和插入实现了递归的回溯，就好像一个个链表在舞台上翩翩起舞一样。

具体的算法实现可以参照 Knuth 的论文，我们还是用图的方式来说明一下。

首先，判断链表是否为空，可以通过 head.right == head 来判断。如果为空则返回，并输出当前的解。
不为空则选择当前节点数最少的列。如果只有列头节点，则返回失败。

选择一列

遍历这一列的每个节点，开始进行覆盖操作：
1. 首先将节点所在行作为解的一部分，加入到当前解中；
  
  选择列中的一个节点所在的行
2. 遍历这一行的所有节点，将每个节点所在列都删除掉，同时删除掉与这些列有交集的所有行：
  2a. 遍历节点所在列的每个节点，将每个节点所在行的所有节点从它所在的列中移除掉，同时将列头节点的计数减 1：
```
node.up.down = node.down
node.down.up = node.up
col_node.count -= 1
```
2b. 还要将这一列从链表中移除：
```
col_node.left.right = col_node.right
col_node.right.left = col_node.left
```
移除了选择行的所有列，和每一列有交集的所有行

进入递归调用，判断链表是否为空；
不为空则选择节点数最少的列，再遍历这一列的节点，进行覆盖操作：
移除掉所有节点之后，进入递归调用，发现链表不为空，但节点数最少的列中没有普通节点了，返回失败；
开始做链表的还原操作。注意还原的顺序需要和移除的顺序相反。如果我们是从上至下，从左至右移除节点，那么还原的时候就从右至左，从下至上。否则的话可能会出现问题，导致一个节点被还原多次，这样列中节点的计数就不准确了。
```
node.up.down = node
node.down.up = node
col_node.count += 1
```

并且把删除的列也取消覆盖

col_node.left.right = col_node
col_node.right.left = col_node

递归返回到上一层，还原之后，发现列中没有其他节点可以选择，再返回到上一层，选择下一个节点所在的行。

选择另一个节点所在行
和之前的方法相同，遍历这一行的所有节点，将每个节点所在列都删除掉，同时删除掉与这些列有交集的所有行：

移除了选择行的所有列，和每一列有交集的所有行
再选择节点最少的列，遍历这一列的所有节点的所在行：

选择节点最少的列，遍历这一列的节点所在行
遍历这一行的所有节点，删除掉每个节点所在列，以及与这些列有交集的所有行：

移除了选择行的所有列，和每一列有交集的所有行
再次进入递归调用，判断矩阵不为空，选择节点最少的一列，遍历每个节点，删除掉所在行的所有列，与这些列有交集的所有行，最后我们得到一个空矩阵。

空链表，只剩头节点
此时将得到的解输出，并返回，接下来还要进行还原操作，然后搜索下一个解。

以上就是舞蹈链算法的执行过程。