舞蹈链算法

❶ 动手实现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。

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

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

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

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

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

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

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

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

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

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

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

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

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

上面这个图是一个舞蹈链的结构，描述的是前面 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 的论文，我们还是用图的方式来说明一下。

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

❷ 有没有好的算法编程解决数独的正确答案

有啊，而且各种语言基本都有。
其中比较经典的舞蹈链算法对常见的标准数独来说简直就是秒解！甚至每秒解几千个几万个。