用DLX解sudoku(数独)

最近在做scala99,其中有一道题目P97是sudoku(数独)。一开始我想到的是列举每个空格的可选数字,选择可选数字最少的的格子开始填写。每次填写,修改关联格子的可选数字。再次尝试填写。这里无解条件是存在没有可选数字的格子。还有就是easy或者normal级别的数独一般可选数字都是1个,分批填写很快就能完成。hard或以上就没有那么幸运了,必须猜测然后验证,存在回溯。

这里描述的算法其实就是搜索+启发。启发是选择性地从最少可选数的格子开始。猜测+验证,感觉这个问题属于NP问题。事实上也确实是,而且可以转化为NP完全的精确覆盖问题(Exact Cover),所以这个问题也是NP完全问题。

P97给的答案有两个,第一个就是搜索+启发,第二个是DLX。DLX是Exact Cover的高效解法。本文就是讲如何用DLX来解数独问题的。考虑到scala99上第二个实现大部分都是可变数据,所以我用Java实现了相应算法。

理解代码前先要了解几个概念:

精确覆盖问题

精确覆盖问题是这样一类问题:有一个大集合S,选择其中的部分元素得到集合T0, T1, T2… Tn,这些集合统称为T*,要求你从T*中找到这样的一组集合,使得这组集合(两两不相交)并集为S,换句话说,S中每个元素都再这组集合中出现并且仅出现一次。

举例(参照wikipedia),S为{1, 2, 3, 4},T* = {T0, T1, T2, T3},T0 = {}, T1 = {1, 3}, T2 = {2, 3}, T3 = {2, 4}。这里T1和T3组成S的一个精确覆盖,因为T1和T3两两不相交并且并集为S。

精确覆盖问题可以用矩阵来表述。比如S = {1, 2, 3, 4, 5, 6, 7}, 存在这样一组T*

  • A = {1, 4, 7}
  • B = {1, 4}
  • C = {4, 5, 7}
  • D = {3, 5, 6}
  • E = {2, 3, 6, 7}
  • F = {2, 7}
1 2 3 4 5 6 7
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1

要从矩阵中找出这样几行,使得一列上只有一个1,而且总共有|S|个数个1。答案是{B, D, F}。

X算法

如果要用计算机来解Exact Cover问题的话,即可以尝试解这个矩阵。常规的一个解法称为X算法。在刚才的矩阵上应用X算法,步骤参照wikipedia。

  1. 如果当前矩阵没有列了,表示当前选择的行组成一个解,返回。
  2. 否则,选择一列。这里一般是选择1最少的列c,就像数独启发的那样。
  3. 遍历列c上值为1的行r
  4. (嵌套1)把r作为部分解
  5. (嵌套1)遍历行r上值为1列c2(理论上包括c)
  6. (嵌套2)遍历c2上所有值为1的行r2(理论上包括r)
  7. (嵌套3)删除行r2
  8. (嵌套2)删除列c2
  9. (嵌套1)递归下一个部分解

直接看上面这段代码过程描述可能还是难以理解,如果想具体看算法过程的,可以参考wikipedia上的过程。这里个人只提示下部分算法步骤的目的。第1步显然是没有列也没有行,全部选完了,自然是合理解。第2步也容易理解,选择最少1个数的列,这样关联的行选择就少,搜索相当于是被优化了。然后遍历这个1数量最少的列。每次尝试一行。选择这行后,需要做的事情除了作为部分解之外,还要把这行关联的所有数值为1的列删除,并且把这些列上值为1的行也删除。从集合上来看,你选择了某个集合。含有你这个集合元素的集合都要排除,其次从矩阵中排查你这个集合中得元素关联的矩阵列。因为你选择了这个集合,元素是排他的。

先别急着实现这个算法。因为这个算法有比较多的删除,递归和回溯,事实上还有特殊情况。比如你选择某组集合,但是某列上没有1,这就说明这组集合不是解,必须回溯。考虑到效率,事实上有一个专门的实现,dancing links,又称DLX。DLX不是一个全新的算法,它只是X的一种高效实现。但是很多人称为DLX算法,你可以理解为Dancing Links on X(个人分析)。

DLX算法

DLX的主要内容是用十字链表(一个节点存在上下左右四个节点的指针)来存储稀疏矩阵,同时利用环形链表的删除和恢复来实现X算法中删除行或者列以及相应的回溯。原本在递归算法中,是在栈中保存矩阵来实现回溯的,自然会产生很多中间数据。DLX算法的论文中文版在这里。使用其中一张十字链表图

使用链表来存储矩阵并不是什么少见的事情,只是这里用十字更符合算法需要的操作。第一行为Column Header,最左右为表头(h),算法之中只需要表头即可访问所有数据,同时Column Header中存在每列中1的个数,便于选择1的数量最少的列。算法执行时,需要从列a的1到列b的1,同时也需要从行a的1到行b的1,这里的十字链表正好可以通过指针快速移动和访问。还有一条,隐藏列或行的时候用链表很容易,同时利用栈数据的特性,回溯时重新把数据列或行恢复也很容易。这些就是个人理解的DLX实现X算法的主体思想。

DLX论文中的伪代码

搜索

选择列

覆盖

取消覆盖

接下来讲个人的Java代码实现。注意,先别急着考虑数独,DLX之后你还需要考虑如何构造矩阵,数独如何转换为精确覆盖问题等。
实现十字链接,除了直接实现之外,还有一种用数组模拟的。数组模拟似乎调试更容易些,有需要的可以在看了构造矩阵部分后实现。个人这里是直接实现,为了调试,让每个节点自己的toString中包含了一些信息。

DLX Java实现

节点模型

这里有4个类,第一个抽象类,包含十字链表的上下左右,Head单独,没有值,Column Header包含1的个数和用于调试的index,单元格包含关联的列和行名。没有单独的行元素。

核心代码

基本就是参照DLX的论文实现的,没有增加其他逻辑。因为我分了多个类表示矩阵中的元素,所以实际方法的参数,变量的类型都有可能不同,不过相对来说类型安全些,全是单元格的话,分不清是列头还是行单元格。

矩阵生成

然后是让人感觉麻烦的矩阵生成。用数学的话讲就是建模后的输入。这里直接用之前的那个表格表示的矩阵。以下是我如何矩阵表示到十字链表的。顺便说一句,部分算法感觉本来就是为了数学家解决某些问题而设计的,也算是数学和计算机编程交界的地方,所以数学好的人可能会相对容易,当然也包括类似复杂度计算什么的。不过泛称的算法比如load balance感觉更属于处理策略的范畴,所以与其说更靠近数学,还不如说算法设计能体现一个人利用计算机的资源处理问题的能力。

扯远了,个人生成DLX的十字链表的策略是先Head,后Column Header,然后一行一行加数据。其中Column Header需要随机访问,所以Column Header除了按照链表节点方式构造之外,还需要存放在一个数组中,方便之后按行加数据。

构造Column Header

增加行

解释下这里增加行的过程。每个元素被加在某列的最后一个元素后,同时横向几个元素需要关联,所以你这里会看到appendDown和appendRight。这样,总体的构造过程变成:

之后用DLX解就行。

数独转换为Exact Cover问题

最后讲一下如何将数独问题转换为Exact Cover问题。参照这篇文章,得知转换的重点是确定约束条件,数独的必要条件是

  1. 81个格子中每个格子只能放一个数字
  2. 每一行的数字不能重复
  3. 每一列的数字不能重复
  4. 每一九宫内的数字不能重复
  5. 看起来很简单,但是怎么转换成矩阵。首先,列是所有元素的集合,这里的元素不是1-9,而是约束条件下的抽象元素。比如第1个条件可以表示为1-81号元素,每个元素表示第几个格子是否有元素。第2个条件可以理解为,假如第1行,理论上有1-9,那么有9个元素,总体有9行,所以有9行1-9,即81个抽象元素。依次类推,四个条件表示了4 * 81即324个抽象元素,即324列。那儿行该怎么表示?你选择在数独板的x行y列上填n,那么324中肯定会关联4个元素,分别是第几格,第几行的数字几,第几列的数字几和第几个九宫的数字几,也就是4个抽象元素。那么填了81个数字,理论上肯定会有324个抽象元素,而且应该两两不相交,满足精确覆盖条件。这里行就是x行y列数字n。实际中,因为部分格子已经填好,所以这部分行已经确定。但是未填的格子,理论上可以填1-9(虽然实际上由于限制不太可能),这里不做剪枝,直接把1-9作为x行y列数字n,共9行纳入矩阵,这样假如在没有任何元素的情况下,最多有81 * 9即729行,实际上没那么多,否则人就不能填了,只能靠计算机解。

    这样定义行的代号

    数独输入代码

    search之后的代码是把选择的行归类便于之后输出,在dlx算法中设置部分解的部分直接归类也是可以的。就看你怎么方便了。
    ONE_TO_NINE是9个数字,1~9。每行针对的4列的index需要计算出来,最后一个九宫格的相对那一些,可以一步一步尝试推导,理论上你这个函数也是“Exact Cover”的就行,不存在不同n对用同一个index的情况即可。

    上面的数独的解是,有兴趣的可以验证下。

    完整代码在 https://github.com/xnnyygn/algorithm-learning/tree/master/dancing-link-java
    scala99个人P97的实现在 https://github.com/xnnyygn/scala99/blob/master/src/main/scala/in/xnnyygn/scala99/P97.scala

    参考