用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最少的列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的覆盖（见下）并且返回。

如果 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]。

1 2	对于每个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。

设置 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。

对于每个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;
  }

}

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;
}

@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;
}

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);
}

// 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);

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);
  }
}

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));
}

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

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