Sudoku的Dancing Link解决方案

Tobi.Azrle

Dancing Link果然好牛...拜林舒大牛所赐，用它搞定了数独，速度相当客观……

Vijos1345上的9×9数独：

├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 9ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms

PKU3074上的9×9数独：

Rank	Run ID	User	Memory	Time	Language	Code Length	Submit Time
1	3891650	azrle	8340K	94MS	Pascal	4848B	2008-08-13 14:59:06
2	3114298	shangjingbo	760K	687MS	Pascal	3354B	2008-02-22 16:28:42
3	3647508	oppo0123456789	904K	704MS	Pascal	2443B	2008-07-15 22:24:07

PKU3076上的16×16数独:

Rank	Run ID	User	Memory	Time	Language	Code Length	Submit Time
1	3273039(2)	frank12268	1440K	719MS	Pascal	8123B	2008-04-08 02:18:57
2	3892286	azrle	2492K	1204MS	Pascal	4855B	2008-08-13 16:02:19
3	3299207(4)	peter112358	1044K	2344MS	Pascal	14086B	2008-04-13 20:38:11
4	3299818(2)	yaliyali	1368K	6375MS	Pascal	6751B	2008-04-13 22:16:08
5	3299815	Cheryl	1368K	6375MS	Pascal	6896B	2008-04-13 22:15:41

相较之下Dancing Link要快得多。。。

不过确实不好编（我比较差，编了好久……）

以下记录数独用Dancing Link的做法：

对于Exact Cover问题，Knuth提出了一种Algorithm X的算法来解决，而Dancing Link(DLX)是一种高效的实现工具。所谓Exact Cover就是，对于一个boolean表，取出其中若干行，使得，每一列有且仅有一个1。

我们首先要把数独问题转化成Exact Cover问题，这里以3×3为例。

构造这样一个boolean表：

（1）行：行是二维的，即存有两种属性，分别是po和num，即在po位置填入数字num

（2）列：列长27×9＋81；前面9个长度为27个区域，后面81个区域。第i个长度为27的区域的第j列，表示填入i，规则j生效，即boolean表为true（规则1～9表示，行规则；规则10～18，列规则；规则19～27，9个框框规则）。

之后我们就可以DLX了：

标记为覆盖状态, 覆盖操作如下：

Cover(x)：x^.reft^.right ← x^.right, x^.right^.left ← x^.left

回溯的时候我们需要将一个已删除的点恢复：

Recover(x)：x^.right^.left← x, x^.left^.right←x

Dancing Links则是基于这样一个用循环链表来维护所有未覆盖的元素的思想, 它是一个四个方向的循环链表结构(circular doubly linked list), 而每个结点对应的是矩阵中所有的1, 另外新建U + 1个虚拟结点, 分别表示一个头结点h和U个结点表示每一列最上方的结点．每个结点记录五个信息：

left, right：表示它所在的行它左边的节点和右边的节点(由于是循环链表, 每一行最左边的结点的left指针指向这一行的最后一个结点, 最后一个结点的right指针指向这一行的第一个结点)．

up, down：表示它所在的列的上方的节点和下方的节点(每一列的第一个结点的up指针指向这一列的最后一个结点, 最后一个结点的down指针指向第一个结点)．

loc：指向它所在的列的最上方的结点．

上面这个图中, 可以非常清晰地看到这个循环链表的结构：第一行为建立的虚拟结点, h为头结点．这个结构将元素之间巧妙地联系在了一起, 下面来看如何让这个优美的结构来实现Algorithm X：

对于每一列, 附加维护一个size[]值表示这一列中的结点个数(不包括最上面第一个结点), 这样每次找一个size[]值最小的未删除的列来代替任意找一列, 会高效很多．

首先定义一个Cover(p)过程, 表示删除p所对应的这一列, p为这一列的最上方的结点．

Procedure Cover(p)

p^.right^.left ← p^.left

p^.left^.right ←p^.right

for (i = p^.down; i != p; i ← i^.down)

for (j = i^.right; j != i; j ← j^.right)

j^.down^.up ← j^.up, j^.up^.down←j^.down, size[j^.loc]-=1

表示将p这一列的每个结点所在的行的所有结点全部删去, 且将p从第0行的链中删去．同理, 定义Recover(p)表示将p这一列恢复, Recover(p)和Cover(p)过程类似：

Procedure Recover(p)

p^.left^.right ← x

p^.right^.left ← x

for (i = p^.up; i != p; i ← i^.up)

for (j = i^.left; j != i; j ← j^.left)

j^.up^.down ← j, j^.down^.up←j, size[j^.loc]+=1

有了这两个基础操作后, Algorithm X算法的实现就比较简单了：

Procedure Algorithm_X(Dep)

如果h^.right = h(即所有的列均被删除), 找到一组解, 退出．

利用h和right指针找到一个c, 满足size[c]最小．

如果size[c] = 0(当前列无法被覆盖), 无解, 退出．

Cover(c)

for (i = c^.down; i != c; i ← i^.down)

for (j = i^.right; j != i; j ← j^.right) Cover(j^.loc)

将i结点加入Ans, Algorithm_X(Dep + 1)

for (j = i^.left; j != i; j ← j^.left) Recover(j^.loc)

Recover(c)

（DLX部分修改自大牛文章，大牛在文章中放了严重的错误，这里已经予以纠正）