每日算法 — 使用java实现数独：DLX舞蹈链与精确覆盖求解

数独是最适合讲”问题建模”的游戏。大多数人第一次写数独求解器，走的是回溯 + 位掩码的路子：每格试 1~9，冲突就退。它能跑，但代码里塞满了”检查行、检查列、检查宫”三种约束的重复逻辑，剪枝效果完全依赖你自己写的启发式。

换一个视角看：数独其实是一个精确覆盖（Exact Cover）问题——把每个候选填法看成”选或不选”，要求每个约束恰好被满足一次。一旦这样建模，求解器就变成了 Donald Knuth 在 2000 年提出的 Algorithm X，而它的高效实现就是舞蹈链（Dancing Links, DLX）。

本文从建模开始，一步步把数独变成 729 行 × 324 列的 0/1 矩阵，再用双向十字链表把它跑起来。

一、把数独翻译成精确覆盖

精确覆盖问题的标准形式是：给定一个 0/1 矩阵，选出若干行，使得每一列恰好有一个 1。

数独有四类约束，每类都要求”恰好一次”：

合计 324 列。

矩阵的行对应”候选填法”：在 (r, c) 填数字 d，是一行。总共 9×9×9 = 729 行。

关键在于：每个候选填法恰好触及 4 个约束——它占用 (r,c) 这一格，同时满足第 r 行的 d、第 c 列的 d、第 b 宫的 d。所以矩阵每行恰好有 4 个 1。

行号编码：rowId = (r * 9 + c) * 9 + (d - 1)

          cell(r,c)  rowNum(r,d)  colNum(c,d)  boxNum(b,d)
rowId 0  [ 1        1            1            1          ]   (0,0,1)
rowId 1  [ 1        1            1            1          ]   (0,0,2)
...
rowId 728[ 1        1            1            1          ]   (8,8,9)

四类列在数组中的偏移分别是 0、81、162、243，这样可以避免用二维数组存列号：

static int cellCol(int r, int c) { return r * 9 + c; }
static int rowNumCol(int r, int d) { return 81 + r * 9 + (d - 1); }
static int colNumCol(int c, int d) { return 162 + c * 9 + (d - 1); }
static int boxNumCol(int r, int c, int d) {
    int b = (r / 3) * 3 + (c / 3);
    return 243 + b * 9 + (d - 1);
}

二、舞蹈链：为什么它叫”舞蹈”

朴素回溯在”选定一行后排除冲突列”时，需要扫描整个矩阵把相关列的所有 1 清掉，回溯时再全部恢复——每次都是 O(矩阵大小) 的复制或重扫。这是 Algorithm X 的最大瓶颈。

Knuth 的洞察是：既然矩阵里 1 的个数在求解过程中只会被”临时删掉”和”原样恢复”，那就用双向循环十字链表来存这些 1。删除一个节点只需改动它上下左右四个邻居的指针，恢复时按相反顺序改回来——指针像跳舞一样翻转，所以叫 Dancing Links。

     ┌───┐
     │ C │  列头节点，size 记录该列还有多少个 1
     └─┬─┘
   ┌───┴───┐
   │  A    │  ← 该列上的某个 1（同时属于某一行）
   └───┬───┘
   ┌───┴───┐
   │  B    │
   └───┬───┘
       └──→ 回到列头 C（循环）

每个普通节点同时处在两条链上：纵向（同一列）和横向（同一行）。所以覆盖一列时，只要沿列向下走，对每个节点再沿它的行向右走，把那些节点从各自的列中”摘除”即可。

节点定义

static class Node {
    Node left, right, up, down;
    Node col;       // 指回所属列的列头
    int size;       // 仅列头有意义：该列当前 1 的个数
    int rowId;      // 该节点所属矩阵行编号，用于还原答案

    Node() { left = right = up = down = this; }   // 自环，表示空链
}

Node() 构造里把自己四个指针都指向自己，这是空双向循环链表的标准写法——插入节点时不用特判”链表为空”。

cover：覆盖一列

/**
 * 覆盖第 c 列：
 * 1) 先在列头层面把 c 从横向链表摘掉（这样后续选列时看不到它）；
 * 2) 再沿 c 的纵向链，把每一行中除 c 之外的节点从它们各自的列里摘掉。
 */
static void cover(Node c) {
    c.right.left = c.left;          // 1) 摘除列头
    c.left.right = c.right;
    for (Node i = c.down; i != c; i = i.down) {          // 2) 遍历该列所有 1
        for (Node j = i.right; j != i; j = j.right) {    // 沿该行遍历（j 最终绕回 i）
            j.down.up = j.up;                            // 从纵向链摘除 j
            j.up.down = j.down;
            j.col.size--;                                // 该列的计数减 1
        }
    }
}

uncover：逆操作

/**
 * 恢复第 c 列。必须严格按 cover 的逆序进行：
 * cover 是先沿 down 遍历、每行沿 right 遍历；uncover 就沿 up、每行沿 left。
 * 顺序反了会导致被摘除的链断在中间。
 */
static void uncover(Node c) {
    for (Node i = c.up; i != c; i = i.up) {
        for (Node j = i.left; j != i; j = j.left) {
            j.col.size++;
            j.down.up = j;          // 重新接上纵向链
            j.up.down = j;
        }
    }
    c.right.left = c;               // 最后恢复列头
    c.left.right = c;
}

这里的”逆序”不是形式主义。cover 从 c.down 开始，每个节点 i 的行的 right 方向被摘除；要可靠地恢复，必须从 c.up 开始、沿 left 方向——因为节点被摘除后它的 up/down/left/right 指针本身没变（只是邻居不再指向它），所以反向遍历是可行的。

建表

static void build(int[][] puzzle) {
    root = new Node();
    colHeaders.clear();

    // 1) 创建 324 个列头，横向串在 root 上（尾插法，保持顺序）
    for (int i = 0; i < 324; i++) {
        Node c = new Node();
        c.size = 0;
        c.up = c.down = c;
        c.right = root;
        c.left = root.left;
        root.left.right = c;
        root.left = c;
        colHeaders.add(c);
    }

    // 2) 为每个候选填法建一行，插入 4 个节点
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            int given = puzzle[r][c];
            for (int d = 1; d <= 9; d++) {
                if (given != 0 && given != d) continue;   // 题目已给定的数字之外全部跳过
                int rowId = (r * 9 + c) * 9 + (d - 1);
                List<Node> rowNodes = new ArrayList<>(4);
                rowNodes.add(insertNode(colHeaders.get(cellCol(r, c)), rowId));
                rowNodes.add(insertNode(colHeaders.get(rowNumCol(r, d)), rowId));
                rowNodes.add(insertNode(colHeaders.get(colNumCol(c, d)), rowId));
                rowNodes.add(insertNode(colHeaders.get(boxNumCol(r, c, d)), rowId));
                linkRow(rowNodes);
            }
        }
    }
}

/** 尾插法在列头下方插入一个节点 */
static Node insertNode(Node c, int rowId) {
    Node n = new Node();
    n.col = c;
    n.rowId = rowId;
    n.up = c.up;
    n.down = c;
    c.up.down = n;
    c.up = n;
    c.size++;
    return n;
}

/** 把同一行的 4 个节点横向串成循环双向链表 */
static void linkRow(List<Node> rowNodes) {
    for (int i = 0; i < rowNodes.size(); i++) {
        Node n = rowNodes.get(i);
        Node next = rowNodes.get((i + 1) % rowNodes.size());
        n.right = next;
        next.left = n;
    }
}

一个容易被忽略的优化：建表时就过滤掉题目给定的格子。给定 (r,c)=5 时，我们只保留 d=5 的那一行，跳过 d=1..4,6..9 的 8 行。这相当于在构建阶段就做了一次强制的”预先覆盖”，直接砍掉约 80% 的矩阵规模。

三、Algorithm X 的递归主体

Algorithm X 的伪代码只有五行，但它完整表达了精确覆盖的搜索逻辑：

1. 如果矩阵为空，找到解；
2. 否则选一个含 1 最少的列 c；
3. 对 c 中每个 1 所在的行 r：把 r 加入解，覆盖 r 的所有列，递归；
4. 若递归失败，撤销覆盖，换下一行；
5. 若所有行都失败，恢复 c，返回失败。

第 2 步的”选 1 最少的列”是最重要的启发式。它是最少候选原则（Minimum Remaining Values）在精确覆盖上的体现：候选最少的列最容易产生矛盾，尽早让它决策，能最快发现死路。这个简单的规则能把数独求解的节点数从数万压到数千。

/** 启发式选列：返回当前 1 个数最少的列头 */
static Node chooseColumn() {
    int best = Integer.MAX_VALUE;
    Node bestCol = null;
    for (Node c = root.right; c != root; c = c.right) {
        if (c.size < best) {
            best = c.size;
            bestCol = c;
            if (best == 0) break;     // 有列为空 -> 当前分支必然失败，提前退出
        }
    }
    return bestCol;
}

static boolean search(int depth) {
    nodesVisited++;
    if (root.right == root) {          // 所有列都被精确覆盖 -> 找到解
        answerCount = depth;
        return true;
    }
    Node c = chooseColumn();
    if (c == null || c.size == 0) return false;

    cover(c);
    for (Node r = c.down; r != c; r = r.down) {
        answer[depth] = r.rowId;                       // 选中这一行
        for (Node j = r.right; j != r; j = j.right) cover(j.col);   // 覆盖该行其余列
        if (search(depth + 1)) return true;            // 深层递归
        for (Node j = r.left; j != r; j = j.left) uncover(j.col);   // 回溯：逆序恢复
    }
    uncover(c);
    return false;
}

注意 root.right == root 这个终止条件：root 是总头节点，所有 324 个列头串在它的横向链上。当所有列都被覆盖摘除后，root 的左右指针互相指向自己，此时链空，说明每一列都恰好被满足了。

另外 cover(j.col) 那两行循环里用的是 r.right 和 r.left——因为 c 已经被 cover 掉了，r 所在的这一行中，c 之外的其他 3 个节点还在各自的列里，需要一并覆盖。这也是为什么 linkRow 必须把 4 个节点串成环：j != r 的循环条件依赖这个环结构。

四、还原棋盘

answer[depth] 里存的是被选中的 rowId。由于 rowId = (r*9+c)*9 + (d-1)，反解非常直接：

static int[][] toGrid(int[] chosen) {
    int[][] g = new int[9][9];
    for (int i = 0; i < chosen.length; i++) {
        int rowId = chosen[i];
        int d = rowId % 9 + 1;          // 数字 1..9
        int cell = rowId / 9;           // 格子编号 r*9+c
        g[cell / 9][cell % 9] = d;
    }
    return g;
}

因为已有解保证每格恰好被填一次，所以这里不需要判重。

五、完整项目结构与运行结果

sudoku/
├── SudokuDlx.java        // 主类：十字链表 + Algorithm X + 输出
└── README.md

用”世界最难数独”之一（芬兰数学家 Arto Inkala 设计）实测：

题目：
8 . . | . . . | . . .
. . 3 | 6 . . | . . .
. 7 . | . 9 . | 2 . .
------+-------+------
. 5 . | . . 7 | . . .
. . . | . 4 5 | 7 . .
. . . | 1 . . | . 3 .
------+-------+------
. . 1 | . . . | . 6 8
. . 8 | 5 . . | . 1 .
. 9 . | . . . | 4 . .

解答：
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

耗时 18 ms，递归节点数 1493，使用行数 81

18 毫秒、1493 个递归节点。作为对比，朴素回溯在这道题上通常需要几十万到上百万次试探——而且这还是 Java 冷启动的环境，JIT warmed up 后通常能压到 3~5 毫秒。

六、DLX 真正的价值：不止数独

把数独建成精确覆盖矩阵后，你会发现同样的框架可以解一整类”拼装”问题：

N 皇后用 DLX 求解是教科书级的例子：81 列（9 行 + 9 列 + 17 主对角 + 17 副对角），每行落子产生 4 个 1。因为 DLX 会自动处理”同一对角线只能有一个皇后”的约束，代码比手写回溯短得多，而且速度快一个数量级。

有三条实战经验值得记下：

1. size 一定要在 cover/uncover 里同步维护。忘了 j.col.size-- 会导致选列启发式失效，性能直接掉一个数量级，而且不报错——这是最难查的 bug。
2. 求全部解时不要提前 return。把 if (search(...)) return true; 改成先记录解、再继续循环，并把 uncover(c) 放在循环之后，就能枚举所有解。
3. 按行数升序建表能让内存局部性更好，构建时间可降 20%~30%；但对求解阶段影响不大，因为求解阶段的关键是 size 排序与指针跳转。

舞蹈链最优雅的地方在于，它把”删掉又恢复”这个操作变成了常数时间的指针翻转，让 Algorithm X 从一份伪代码变成了真正能跑得飞快的工程实现。理解了它，你就掌握了处理一大类组合约束问题的通用武器。