Dancing Link在数独求解中的应用

柯建平 陈昱宇

泉州市儿童医院

“数独”（sudoku）一词来自日语，意思是“单独的数字”或“只出现一次的数字。”概括来说，它就是一种填数字游戏。数独作为人类的一种经典的益智游戏，它的计算机解决对于人们对计算机能做什么，可以做到怎样有很大的启发意义，本文从搜索的角度，也是最基本的一种方法，但是对其程序实现的一个较大的优化，使用Dancing Link 技术，十字链表的使用和启发式的搜索方法，大大提高了程序的运行效率。

双向链表又叫双链表，是链表的一种。双向链表的存储结构往往是有一个空的结点来表示头指针。然后每一个结点有一个直接前驱值域和一个直接后驱值域。

如果是十字链表的话，结点中指针的值域会变成四个。在单向链表中删除一个结点是非常麻烦，而且低效的。双向链表有着优美的结构，可以方便的删除任意一个结点。公式如下：L[R[x]] = L[x]； R[L[x]] = R[x]；其中x指的是编号，LR来记录左右方向的双向链表。

这边用的静态数组的实现方式，同指针其实是一样的，如果你实现过双向链表的话，那你一定会觉得很熟悉。双向链表的结点恢复，请看公式如下：L[R[x]] = x； R[L[x]]= x； 其中x指的是编号，LR来记录左右方向的双向链表[4]。

Dancing Links的核心思想就是对于稀疏矩阵采用双向十字链表存储的搜索[5]。对于双向链表结点删除和恢复操作，大家在平时只想怎样删除，而从没想过把删除掉的结点恢复。有些人可能觉得这是不好的，如果没有把分配出去的内存删除掉，很容易造成内存泄漏。但这里，我们却需要这样做。我们在链表中删除结点，只做标记，不做真正的清空内存操作。这样我们后来便可以用(2) 进行恢复操作了。(2)才是Dancing Links的核心.接下来我们来看一个经典的搜索问题，精确覆盖问题：

给定一个由0和1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1？例如，下面这个矩阵

图1-1 矩阵

就包含了这样一个集合（第1，4，5行）。我们把列想象成全集的一些元素，而行看作全集的一些子集；或者我们可以把行想象成全集的一些元素，而把列看作全集的一些子集；那么这个问题就是要求寻找一批元素，它们与每个子集恰好有一个交点。这是一个NP问题。自然，作为首选的算法就是回溯了。下面给出算法过程：

上述代码和普通的搜索本质上是相同的，但看上去不太一样我在下面将会给出源码。这段代码的算法框架已经固定了 ，几乎没有可优化的余地，就算用非递归来优化也不会得到多少的效率提升，反而会使编码复杂度和出错率大大增加。如何去实现代码行(1) (2) (3) (4) 是优化的关键，也是Dancing Links发挥其作用的地方。我们可以直观的去想到一个简单的方法：

Step (1)：把矩阵进行扫描，选出未做删除标记的列中元素个数最少的。

Step (2): 对当前列和行做标记，标记其已经删除。

Step (3): 同Step (2)

Step (4): 把相应的标记删除。

Step (5): 同Step (4)

然而，这个方法很明显是非常低效的，做标记是快速的。但是相应的带来的问题，是查找的时候会变得非常慢。复杂度始终是O(n)(n为矩阵大小)。在step (1) (2) (3) (4)(5) 中我们都用到了查找操作，所以我们不能忽视查找的复杂度。在这个实现方式中，把查找的效率提升多少，整个程序便可提升多少。

下面我们来细细展开Dancing Links的双向十字链表。

由于经常要用到2级指针，如果用真正的指针实现的话代码可读性很差，代码也不好看，所以我用静态数组实现，这样既可方便的建立矩阵，也可以加快运行速度。对每一个对象，记录如下几个信息：

L[x], R[x], U[x], D[x], C[x]；

双向十字链表用LRUD来记录，LR来记录左右方向的双向链表，UD来记录上下方向的双向链表。 head 指向总的头指针，head通过LR来贯穿的列指针头。 每一列都有列指针头。C[x]是指向其列指针头的地址。行指针头可有可无，在我的实现中没有显示的表示出来。在某些题目中，加个行指针头还是很有必要的。

另外，开两个数组cnt[x], ans[x]；cnt[x]记录列链表中结点的总数。ans[x]用来记录搜索结果。

本设计主要研究Dancing Links算法与实现。本文设计了精确覆盖模型的建立模型建立并编程实现，通过暴力搜索算法的比较，得出Dancing Links搜索时间上的明显的优势。Dancing Links与暴力搜索的搜索时间相差在100倍以上。