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数独:
PKU3076上的16×16数独:
相较之下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部分修改自大牛文章,大牛在文章中放了严重的错误,这里已经予以纠正)