Dancing Links与数独

『Dancing Links与数独』

写这篇文章是为了介绍一个数独破解算法,在你看到真正的破解算法之前,我会做一个不短的铺垫,这应该对于真正理解算法的思想是重要的。

一个容易忽视的链表技巧

在处理双向链表的时候,删除一个节点x的操作是这样的:

L[R[x]]←L[x],R[L[x]]←R[x]

其中L[x]表示x的前驱节点,R[x]表示x的后继节点。
但很少有人意识到还可以通过以下操作将x重新恢复到链表中:

L[R[x]]←x,R[L[x]]←x

一般情况下,我们不希望删除的节点还能重新链接回链表,不彻底的删除具有潜在的危险性。不过,评判一个操作的好坏取决于它的使用坏境,比如在回溯程序中,我们必须在某路径失败后,使程序回溯到原来的状态。

我们下面介绍的DancingLinks算法,正是通过这种手段还原的。

精确覆盖问题

DancingLinks正是为了解决一个这样的一般问题:给定一个0,1为元素的矩阵,能否找到一个行的集合,使得集合中每一列都恰好只包含一个1。

比如下面这个矩阵

$$\begin{pmatrix}0& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 1& 0& 0& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 1& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 1& 0&1 \end{pmatrix}$$

就包含了这样一个行的集合(第1行,第4行,第5行)。

我们可以把所有列想象为全集的元素,把行想象为包含某些列元素(为1的那些)的一个子集(或者行列换过来),那么问题就变成,寻找全集的一个划分。也即寻找一个子集的集合,使得每个元素都属于某一个子集,且仅属于那个子集。

显然这不是一个容易的问题,而且已经证明这是一个NP-完全问题【附录】,也是卡普的二十一个NP-完全问题之一。首选算法就是回溯了。

DancingLinks算法

现在正式介绍一下这个算法,Knuth称他为X算法,对于要处理的 0,1矩阵A:

如果A为空,问题解决;返回成功。
否则,选择一个列c(确定的)。
选择一个使得A[r,c]=1的行r(非确定的)。
将r包含进部分解。
对于每一个使得A[r,j]=1的j
         从A中删除列j
         对于每一个使得A[i,j]=1的i
                   从A中删除行i
在不断变小的A上,递归的重复上述算法。

算法在选取了不同的行r之后,裂变成不同的子算法,子算法之间是相互独立的;每一个子算法都包含一个当前的A矩阵,只是这个A矩阵根据行r进行了相应的删减。当列c只有0元素的时候,子算法返回失败。

自然的,这些子算法构成了一棵搜索树,第k层的每个子算法对应了选择的那k个不同的行。这个回溯算法使先序遍历了这棵树,也就是深度优先搜索。

对于任何选择列c的顺序,算法都可以得到所有解。但不同的选择顺序将使得搜索树的规模相去甚远。为了使搜索树获得最少的节点数目,每次都应该选择包含1最少的那个列c。Knuth的论文显示在一些较大规模的场景下,这样做会比随机选择搜索的节点数减少一个数量级。

好了,我们来看一下算法具体是怎么构建起来的,并且是怎么应用上那个“删除-恢复节点”的技巧的。

Let’s Dance

将矩阵A中的每个元素1用一个具有五个域L[x],R[x],U[x],D[x],C[x]的数据对象x来表示。矩阵的每行都是一个环形的双向链表,通过L,R两个域连通(left and right);每一列也是一个环形的双向链表,通过U,D两个域连通(up and down)。每一列还包含一个特殊的数据对象——列表头。

每个列表头都是一个更大一点的数据对象y。y包含七个域L[y],R[y],U[y],D[y],C[y]和另外两个增加的域S[y](size)和N[y](name);S[y]表示的是这一列中元素1的个数,一方面为列的选择顺序提供依据,另一方面当值为0时返回失败。N[y]为这个列的名称,用于最后答案的输出。而以上所有对象中的域C都指向本列的列表头。

对于列表头通过L和R组成的环形双向链表,同样包含一个特殊的列表头对象h,可以把它当做整个数据结构的根。而且它的U[h],D[h],C[h],S[h]和N[h]是用不到的。

如果我们把上面那个0,1矩阵(列命名为A、B、C、D、E、F、G)作为例子用这些数据对象表示出来,就是下面这样:

:图中在上下左右处是相连的环形。而且没有画出C域,那样做会把图弄乱。列表头中标出的是列名和元素1的个数。

 

下面给出搜索过程search(k)的明晰的形式,当然在开始时,k=0:

If R[h]=h,输出当前解,返回成功。
Else 选择一个列c
If c非空,Cover(c)。
Else 返回失败。
For each r←D[c],D[D[c]],……,while r≠c
         Set \(O_{k}\)←r
         For each j←R[r],R[R[r]],……,while j≠r
                   Cover(j)
         Search(k+1);
         Set r←\(O_{k}\),c←C[r]
         For each j←L[r],L[L[r]],……,while j≠r
                   Uncover(j)。
Uncover(c)返回失败。

  1. 输出当前解

很简单,我们已经得到了一个关于行的序列\(O_{0}\),\(O_{1}\),\(O_{2}\),……,\(O_{k-1}\)。最终我们需要的答案是一个行的集合,而这个序列中每一个对象对应某行中的一个元素1,而且我们知道,行与行之间没有重复,当得知这一行中哪些列元素值为1的时候,我们就可以唯一的确定这个行。所以只要输出N[C[O]],N[C[R[O]]],N[C[R[R[O]]]]……就代表了那一行,输出所有的O即为解。

  1. 选择一个列c

如果为了省事,可以简单的Set c←R[h]。

如果想获得最小分支的搜索树,可以

Set s←\(\infty\)
For each j←R[h],R[R[h]],……,while j≠h
         If S[j]<s set c←j and s←S[j].

这样我们就得到了包含1最少的那一列c。

  1. Cover操作

Cover操作是这样的,首先从列表头中删除c,然后遍历列c所有的对象,删除这些对象所在的行里面不是列c的那些对象。

Set L[R[c]] ← L[c] and R[L[c]] ← R[c].
For each i ← D[c], D[D[c]], . . . , while I ≠ c,
         for each j ← R[i], R[R[i]], . . . , while j ≠ i,
                  set U[D[j]] ← U[j], D[U[j]] ← D[j],
                  and set S[C[j]] ← S[C[j]] − 1.

这就是我们在文章开头提到的删除节点的操作。

  1. Uncover操作

这就是整个算法的重点了,也就是删除操作的逆操作。

For each i = U[c], U[U[c]], . . . , while i ≠ c,
         for each j ← L[i], L[L[i]], . . . , while j ≠ i,
                  set S[C[j]] ← S[[j]] + 1,
                  and set U[D[j]] ← j, D[U[j]] ← j.
Set L[R[c]] ← c and R[L[c]] ← c.

注意到我们的还原操作和删除操作正好相反。操作时要非常小心。

 

是不是迫不及待的想知道算法是如何运行的了,下面将以前面的矩阵为例说明。

首先是search(0)选择一个最小列A,然后cover(A)

接下来选择A列中的某一行,首先选择的是第一行(A,D,G),然后对这一行中每一个不在A列的对象所在的列进行cover操作。如下图:

接着程序进入search(1),我们把矩阵中访问不到的列去掉,让图示更清晰。又是选择一个最小列B,然后cover(B)

因为列B只有一个对象,所以选择那一行(B,C,F),然后进行一组cover操作,得到下图:

这样做完,我们就来到了search(2),仍然将无法访问的列去掉,得到下图,这时发现只有列E,而且此列为空,说明本次搜索失败,返回。

返回到search(1),并且进行相应的uncover操作,使删除操作得到还原。就还原到下面这张图,此时还在search(1)中。

发现B列只有一行,已经完全遍历,于是uncover(A)回溯到search(0),下图:

由于行(A,D,G)搜索失败,for循环将继续选择A列下一行(A,D),跟着是一组cover操作。

这样我们就来到了另一个分支的search(1),选择最小列E,cover(E).

选择行(C,E,F)一组cover操作后,得到:

接着进入search(2),选择B并cover(B):

选择行(B,G)并进行一组cover操作,得到:

最终我们进入了search(3),然后高兴的发现,R[h]=h,我们得到了一组解。

输出(A,D)(E,F,C)(B,G).

这样我们就使用DancingLinks算法将精确覆盖问题解决了。

一个应用:骨牌拼图问题

骨牌拼图问题是精确覆盖问题的一个经典应用,我们以Scott的12片5格骨牌问题为例:我们有12片骨牌,每片骨牌的大小都是5格,要求将这12片骨牌放入8*8的正方形棋盘中,而且棋盘中间留有一个边长为2的空格。比如下图就是其中的一个解

可以将拼图问题转化为精确覆盖问题,我们想象有一个72列的矩阵,其中60列表示的是棋盘中非中心部分的格子,12列表示12片骨牌。矩阵的每一行表示一片骨牌在棋盘中的一种摆放方案,这一行中有5个1表示放置时压住的格子,还有一个1指示这是哪一片骨牌。如果你列举所有的摆放情况,你将得到1568个这样的行。

r1c1 r1c2 r1c3 r1c4 r1c5 r1c6 …… r8c8 第1片 第2片 …… 第12片
1 1 1 1 1 1 0 0 0 1 0 0 0
2
……
1568

如果我们对“长条形”编号为第一片骨牌,那么表中第一行表示的就是它在下示位置时的情况。

不难想象,精确覆盖编码之后的矩阵,我们就能得到问题的解。如果你有兴趣计算这个问题,将得到65组不同的拼图解。

一种直观解释

这一节,我将试图使用直观形象的解释去说明为什么DancingLinks执行之后,就能得到精确覆盖问题的解。这可能需要一点想象力。

首先我们回到骨牌问题,我们得到的那个矩阵到底意味着什么呢?想象在一个棋盘上,你拿着第一片骨牌“长条形”试图放置在棋盘里,为了获得放置的所有可能性,一种可选的方案是这么做,先选择一种姿态,比如横着,然后从棋盘的左上角开始,按着从左到右,从上到下的顺序依次摆放,直到棋盘的右下角停止,接着把他竖过来,仍然采用同样的方式,这样就得到了第一片骨牌的所有可能位置。当你把所有骨牌的位置都得到之后,就得到了那个1568行的矩阵,这时你可以认为有1568片骨牌,叠加在那个棋盘上。

下面的所有操作都是在这个有着1568片骨牌的棋盘上进行的,认识到这一点很重要。

我们选择一个列c然后cover(c)是什么意思呢?因为一列指代的是棋盘上某一个格子,选择一列即选择那个格子,cover(c)实际上是把所有覆盖到这一个格子的骨牌全部拿走(这里的拿走是说,你通过其他格子上的骨牌,再也无法访问到这个格子)。

接着我们选择了列c中的某一行,进行了一组cover操作,这又代表什么呢?正如之前所说,选择列c的某一行,其实就是在拿走的那些骨牌里面挑一片,然后把这一片压住的格子上面的全部骨牌都拿走,并且使得这些格子在之后都不能被访问。“挑一片”意思是,我先认定挑出来的这一片是正确的,如果这样认为,当然要将和我这一片有交集的其他骨牌全部丢弃才不会发生冲突,因为一个格子只能有一个骨牌。

就这样迭代的选取,直到两种情况下程序可以给出判断,一种是恰好所有的格子都无法访问,这就说明本次挑选的骨牌序列恰好铺满了整个棋盘,于是得到一组解;另一种情况是,程序选取到某一个仍然可以访问的格子时,发现上面已经没有骨牌了,这就说明,这次挑选的骨牌序列不足以铺满整个棋盘,而且也没有合适的骨牌恰好填补这个格子了,这时就会返回失败。

返回失败后,程序将回溯到上一次search的位置,然后在那一打骨牌里面挑选下一片运行,就这样反复试错,直到把所有可能性全部囊括进来。

不知道我的解释是不是让问题更清楚了呢?

数独问题转化为精确覆盖问题

假设我们现在已经完全理解了什么是精确覆盖问题,也知道了DancingLinks算法的含义,那么如果一个问题恰好可以转换为精确覆盖问题,只要给出转换方案,我们就可以求解了,数独问题正好就是这类问题。

数独:在一个9*9格子的盘面上,又被分为3*3个宫,每宫有3*3个格子,格子上会给出已知的数字(1-9),要求根据这些数字,推理出所有剩余格子的数字,并满足每一行、每一列、每一宫内的数字均含1-9,不重复。

一个数独谜题

上面数独的解

实际上一个数独的规则可以总结为以下四条:

1每个格子有一个数字

2每行1-9分别填一遍

3每列1-9分别填一遍

4每宫1-9分别填一遍

下面只需将这些约束规则转换为矩阵的列定义即可:

对于规则1定义如下各列:

格(1,1)有一个数字;

格(1,2)有一个数字;

……

格(9,9)有一个数字;

(共计81列)

对于规则2定义如下各列:

第1行填了数字1

第1行填了数字2

……

第9行填了数字9

(共计81列)

对于规则3定义如下各列:

第1列填了数字1

第1列填了数字2

……

第9列填了数字9

(共计81列)

对于规则4定义如下各列:

第1宫填了数字1

第1宫填了数字2

……

第9宫填了数字9

(共计81列)

因此矩阵共包含324列。

 

那么如何将一个给定的数独问题,转换为一个具体的矩阵呢?对于数独中的格子,要分两种情况,有数字或没有数字。

有数字的格子

比如第1宫里的格(3,2)填了数字9,对应规则得到:

1,格(3,2)有一个数字

2,第3行填了数字9

3,第2列填了数字9

4,第1宫填了数字9

所以“第1宫里的格(3,2)填了数字9”对应的行中,只需将上述四列设置为1,其余列设置为0。

没有数字的格子

比如第2宫格(1,4)数字待填,可以转换为:

第2宫格(1,4)填了数字1

第2宫格(1,4)填了数字2

……

第2宫格(1,4)填了数字9

分别按照有数字的格子的转换方法计算,就能得到矩阵的9行。

 

至此,这样就能把数独问题转化为精确覆盖问题了。

Knuth

DancingLinks算法正是由Knuth发明,他将其归功于Hiroshi Hitotsumatsu与Kōhei Noshita 在1979的研究,但是Knuth的论文让DancingLinks流行。算法的巧妙无需多言。

之所以将其命名为DancingLinks是因为Knuth觉得,算法不断的进行删除和还原的操作,节点的“打开”和“关闭”演奏出一串跳动的音符,好似一位灵动的舞者随之起舞。

参考

  1. Dancing Links. Donald E. Knuth, Stanford University 2000.11
  2. 算法实践——舞蹈链(Dancing Links)算法求解数独http://www.cnblogs.com/grenet/p/3163550.html
  3. 数独http://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8
  4. 舞蹈链http://zh.wikipedia.org/wiki/%E8%88%9E%E8%B9%88%E9%93%BE
  5. 卡普的二十一个NP-完全问题http://zh.wikipedia.org/wiki/%E5%8D%A1%E6%99%AE%E7%9A%84%E4%BA%8C%E5%8D%81%E4%B8%80%E5%80%8BNP-%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C

附录:卡普的21个NP完全问题

  1. 布尔可满足性问题(Satisfiability):对于布尔逻辑内合取范式方程式的满足性问题(一般直接叫做SAT)
  2. 0-1 整数规划(0-1 integer programming)
  3. 分团问题(Clique)(参考独立集)
  4. Set packing(Set packing)
  5. 最小顶点覆盖问题(Vertex cover)
  6. 集合覆盖问题(Set covering)
  7. Feedback node set(Feedback node set)
  8. Feedback arc set
  9. 有向哈密顿循环 (卡普命名,现称Directed Hamiltonian cycle)
  10. 无向哈密顿循环 (卡普命名,现称Undirected Hamiltonian cycle)
  11. 每句话至多3个变量的布尔可满足性问题 (Satisfiability with at most 3 literals per clause, 3-SAT)
  12. 图着色问题(Chromatic number)
  13. 分团覆盖问题(Clique cover)
  14. 精确覆盖问题(Exact cover)
  15. Hitting set(Hitting set)
  16. Steiner tree(Steiner tree)
  17. 三维匹配问题(3-dimensional matching)
  18. 背包问题(Knapsack)
  19. Job sequencing(Job sequencing)
  20. 划分问题(Partition)
  21. 最大割(Max cut)

发表评论

电子邮件地址不会被公开。 必填项已用*标注