最近在做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最少的列c，就像数独启发的那样。
- 遍历列c上值为1的行r
- （嵌套1）把r作为部分解
- （嵌套1）遍历行r上值为1列c2（理论上包括c）
- （嵌套2）遍历c2上所有值为1的行r2（理论上包括r）
- （嵌套3）删除行r2
- （嵌套2）删除列c2
- （嵌套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论文中的伪代码
搜索
如果 R[h]=h ，打印当前的解（见下）并且返回。 否则选择一个列对象c（见下）。 覆盖列c（见下）。 对于每个r←D[c]，D[D[c]]，……，当 r!=c， 设置 Ok<-r； 对于每个j←R[r]，R[R[r]]，……，当 j!=r， 覆盖列j（见下）； search(k+1)； 设置 r←Ok 且 c←C[r]； 对于每个j←L[r]，L[L[r]]，……，当 j!=r， 取消列j的覆盖（见下）。 取消列c的覆盖（见下）并且返回。
选择列
对于每个j←R[h]，R[R[h]]，……，当 j!=h， 如果 S[j]<s 设置 c←j 且 s←S[h]。
覆盖
设置 L[R[c]]←L[c] 且 R[L[c]]←R[c]。
对于每个i←D[c]，D[D[c]]，……，当 i!=c，
对于每个j←R[i]，R[R{i]]，……，当 j!=i，
设置 U[D[j]]←U[j]，D[U[j]]←D[j]，
并且设置 S[C[j]]←S[C[j]]-1。
取消覆盖
对于每个i←U[c]，U[U[c]]，……，当 j!=i， 对于每个j←L[i]，L[L[i]]，……，当 j!=i， 设置 S[C[j]]←S[C[j]]+1， 并且设置 U[D[j]]←j，D[U[j]]←j。 设置 L[R[c]]←c 且 R[L[c]]←c。
接下来讲个人的Java代码实现。注意，先别急着考虑数独，DLX之后你还需要考虑如何构造矩阵，数独如何转换为精确覆盖问题等。
实现十字链接，除了直接实现之外，还有一种用数组模拟的。数组模拟似乎调试更容易些，有需要的可以在看了构造矩阵部分后实现。个人这里是直接实现，为了调试，让每个节点自己的toString中包含了一些信息。
DLX Java实现
节点模型
abstract class AbstractCell {
AbstractCell left;
AbstractCell right;
AbstractCell up;
AbstractCell down;
void appendRight(AbstractCell that) {
right = that;
that.left = this;
}
void appendDown(AbstractCell that) {
down = that;
that.up = this;
}
@Override
public String toString() {
return getDescription();
}
protected abstract String getDescription();
}
class Head extends AbstractCell {
Head() {
left = this;
right = this;
}
@Override
protected String getDescription() {
return "head";
}
}
class ColumnHeader extends AbstractCell {
int numberOfOnes = 0;
int index = -1; // for debug
ColumnHeader() {
up = this;
down = this;
}
@Override
protected String getDescription() {
return "column " + index;
}
}
class Cell<T> extends AbstractCell {
T name;
ColumnHeader columnHeader;
@Override
protected String getDescription() {
if (columnHeader == null)
return "cell " + name;
return "cell " + columnHeader.index + ", " + name;
}
}
这里有4个类，第一个抽象类，包含十字链表的上下左右，Head单独，没有值，Column Header包含1的个数和用于调试的index，单元格包含关联的列和行名。没有单独的行元素。
核心代码
@SuppressWarnings("unchecked")
public <T> void search(Head h, int depth, T[] solution) {
if (h.right == h) {
// System.out.println(Arrays.toString(solution));
return;
}
ColumnHeader column = selectColumn(h);
cover(column);
// iterate each row of this column
for (AbstractCell row = column.down; row != column; row = row.down) {
solution[depth] = ((Cell<T>) row).name;
// cover columns link to row
for (AbstractCell column2 = row.right; column2 != row; column2 = column2.right) {
cover(((Cell<?>) column2).columnHeader);
}
search(h, depth + 1, solution);
// uncover columns link to row
for (AbstractCell column2 = row.left; column2 != row; column2 = column2.left) {
uncover(((Cell<?>) column2).columnHeader);
}
}
uncover(column);
}
private <T> void uncover(ColumnHeader column) {
// unhide current column
for (AbstractCell row = column.up; row != column; row = row.up) {
for (AbstractCell cell = row.left; cell != row; cell = cell.left) {
((Cell<?>) cell).columnHeader.numberOfOnes++;
cell.up.down = cell;
cell.down.up = cell;
}
}
column.right.left = column;
column.left.right = column;
}
private void cover(ColumnHeader column) {
// hide current column
column.right.left = column.left;
column.left.right = column.right;
// iterate each row of column
for (AbstractCell row = column.down; row != column; row = row.down) {
// find cell link to row
for (AbstractCell cell = row.right; cell != row; cell = cell.right) {
cell.down.up = cell.up;
cell.up.down = cell.down;
((Cell<?>) cell).columnHeader.numberOfOnes--;
}
}
}
private ColumnHeader selectColumn(Head h) {
int min = Integer.MAX_VALUE;
ColumnHeader selected = null;
for (AbstractCell cell = h.right; cell != h; cell = cell.right) {
ColumnHeader column = (ColumnHeader) cell;
if (column.numberOfOnes < min) {
selected = column;
min = column.numberOfOnes;
}
}
return selected;
}
基本就是参照DLX的论文实现的，没有增加其他逻辑。因为我分了多个类表示矩阵中的元素，所以实际方法的参数，变量的类型都有可能不同，不过相对来说类型安全些，全是单元格的话，分不清是列头还是行单元格。
矩阵生成
然后是让人感觉麻烦的矩阵生成。用数学的话讲就是建模后的输入。这里直接用之前的那个表格表示的矩阵。以下是我如何矩阵表示到十字链表的。顺便说一句，部分算法感觉本来就是为了数学家解决某些问题而设计的，也算是数学和计算机编程交界的地方，所以数学好的人可能会相对容易，当然也包括类似复杂度计算什么的。不过泛称的算法比如load balance感觉更属于处理策略的范畴，所以与其说更靠近数学，还不如说算法设计能体现一个人利用计算机的资源处理问题的能力。
扯远了，个人生成DLX的十字链表的策略是先Head，后Column Header，然后一行一行加数据。其中Column Header需要随机访问，所以Column Header除了按照链表节点方式构造之外，还需要存放在一个数组中，方便之后按行加数据。
构造Column Header
public ColumnHeader[] buildColumnHeaders(Head head, int length) {
AbstractCell lastColumn = head;
ColumnHeader[] columns = new ColumnHeader[length];
for (int i = 0; i < length; i++) {
ColumnHeader column = new ColumnHeader();
column.index = i;
columns[i] = column;
lastColumn.appendRight(column);
lastColumn = column;
}
lastColumn.right = head;
return columns;
}
增加行
// appendLine(columnHeaders, 'A', new int[] {0, 3, 6});
private <T> void appendLine(ColumnHeader[] columnHeaders, T name, int[] elements) {
if (elements.length == 0)
return;
AbstractCell lastCell = new Cell<T>();
for (int i = 0; i < elements.length; i++) {
Cell<T> cell = new Cell<T>();
ColumnHeader column = columnHeaders[elements[i]];
AbstractCell columnLastCell = column.up;
columnLastCell.appendDown(cell);
column.numberOfOnes++;
column.up = cell;
cell.down = column;
cell.name = name;
cell.columnHeader = column;
lastCell.appendRight(cell);
lastCell = cell;
}
AbstractCell firstCell = columnHeaders[elements[0]].up;
lastCell.appendRight(firstCell);
}
解释下这里增加行的过程。每个元素被加在某列的最后一个元素后，同时横向几个元素需要关联，所以你这里会看到appendDown和appendRight。这样，总体的构造过程变成：
Head h = new Head();
ColumnHeader[] columnHeaders = DancingLinks.buildColumnHeaders(h, 7);
appendLine(columnHeaders, 'A', new int[] {0, 3, 6});
appendLine(columnHeaders, 'B', new int[] {0, 3});
appendLine(columnHeaders, 'C', new int[] {3, 4, 6});
appendLine(columnHeaders, 'D', new int[] {2, 4, 5});
appendLine(columnHeaders, 'E', new int[] {1, 2, 5, 6});
appendLine(columnHeaders, 'F', new int[] {1, 6});
// Character[] solution = new Character[6];
// dancingLinks.search(h, 0, solution);
之后用DLX解就行。
数独转换为Exact Cover问题
最后讲一下如何将数独问题转换为Exact Cover问题。参照这篇文章，得知转换的重点是确定约束条件，数独的必要条件是
- 81个格子中每个格子只能放一个数字
- 每一行的数字不能重复
- 每一列的数字不能重复
- 每一九宫内的数字不能重复
看起来很简单，但是怎么转换成矩阵。首先，列是所有元素的集合，这里的元素不是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行，实际上没那么多，否则人就不能填了，只能靠计算机解。
这样定义行的代号
class SudokuCell {
int x;
int y;
int n;
SudokuCell(int x, int y, int n) {
super();
this.x = x;
this.y = y;
this.n = n;
}
@Override
public String toString() {
return String.format("(%d, %d) -> %d", x, y, n);
}
}
数独输入代码
public void test() {
Head h = new Head();
ColumnHeader[] columnHeaders = DancingLinks.buildColumnHeaders(h, 324);
String sudoku =
".3..9..5.\n....1...4\n5..8....7\n....3.2..\n6....9.4.\n..7..25..\n.....19..\n..69....8\n12.....7.";
String[] lines = sudoku.split("\n");
for (int y = 0; y < lines.length; y++) {
char[] chars = lines[y].toCharArray();
for (int x = 0; x < chars.length; x++) {
char c = chars[x];
if (c == '.')
appendSudokuCell(columnHeaders, x, y);
else
appendSudokuCell(columnHeaders, x, y, c - '0');
}
}
SudokuCell[] solution = new SudokuCell[81];
dlx.search(h, 0, solution);
int[][] board = new int[9][9];
for (SudokuCell cell : solution) {
board[cell.y][cell.x] = cell.n;
}
for (int y = 0; y < 9; y++) {
for (int x = 0; x < 9; x++) {
System.out.print(board[y][x]);
System.out.print(' ');
}
System.out.println();
}
}
private void appendSudokuCell(ColumnHeader[] columnHeaders, int x, int y) {
for (int n : ONE_TO_NINE) {
appendSudokuCell(columnHeaders, x, y, n);
}
}
private void appendSudokuCell(ColumnHeader[] columnHeaders, int x, int y, int n) {
appendLine(columnHeaders, new int[] {x + y * 9, y * 9 + n - 1 + 81, x * 9 + n - 1 + 162,
9 * (x / 3) + 27 * (y / 3) + n - 1 + 243}, new SudokuCell(x, y, n));
}
search之后的代码是把选择的行归类便于之后输出，在dlx算法中设置部分解的部分直接归类也是可以的。就看你怎么方便了。
ONE_TO_NINE是9个数字，1~9。每行针对的4列的index需要计算出来，最后一个九宫格的相对那一些，可以一步一步尝试推导，理论上你这个函数也是“Exact Cover”的就行，不存在不同n对用同一个index的情况即可。
上面的数独的解是，有兴趣的可以验证下。
7 3 4 2 9 6 8 5 1 2 6 8 5 1 7 3 9 4 5 9 1 8 4 3 6 2 7 9 1 5 7 3 4 2 8 6 6 8 2 1 5 9 7 4 3 3 4 7 6 8 2 5 1 9 8 5 3 4 7 1 9 6 2 4 7 6 9 2 5 1 3 8 1 2 9 3 6 8 4 7 5
完整代码在 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