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

一、从肯肯说起

肯肯（KenKen，又叫 Calcudoku、贤者之数）是日本教师宫本哲也发明的一款算术逻辑谜题。它的规则只有两条：

1. 在 n×n 的棋盘里填入 1~n，使每一行、每一列都不重复（即构成一个 n 阶拉丁方）；
2. 棋盘被划分为若干个粗线框（称为 cage，笼子），每个笼子左上角标有「目标值 + 运算符」，笼内数字必须通过该运算符组合成目标值。减法和除法笼子固定为两格，且要求「大数减小数 / 大数除以小数」得到目标值。

一个 4×4 的肯肯棋盘，其 cage 可以是这样划分的：

+-------+----+--------+
| 6×    | 2- | 4×     |
| (0,0) |    |        |
+---+---+----+----+---+
|   |   |    |    |1- |
+---+---+----+----+---+
|4÷ | 9×      |    |   |
+---+---------+----+---+

看起来比数独简单，实际上它更难用「候选数」这种直觉手段压缩：数独的单格约束是「不等于某个数」，而肯肯的 cage 约束是跨格的算术关系，一格变化会同时影响整笼的可行性。这正是精确覆盖（Exact Cover）建模与约束传播的用武之地。

二、精确覆盖问题与 Dancing Links

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

Donald Knuth 提出的 Algorithm X 用「回溯 + 最小列优先」求解它，而 Dancing Links（DLX）用双向十字链表让「删除列 / 恢复列」变成 O(1) 的指针操作，使回溯性能提升一到两个数量级。数独是这个模型的经典案例：

• 列：每格的「已填」1 组 n² + 每个「行-值」对 n² + 每个「列-值」对 n² = 3n² 列；
• 行：每个候选 (r, c, v) 对应一行，它在「格 (r,c)」「行 r 取 v」「列 c 取 v」三列上各放一个 1。

选出一组行恰好覆盖 3n² 列，就等价于「每格填一个数、每行每值出现一次、每列每值出现一次」——正好是拉丁方约束。肯肯的硬约束与拉丁方完全相同，所以可以直接复用这套矩阵。

肯肯与数独的差别只有一层：额外的 cage 算术约束。精确覆盖矩阵天然只能表达「某列恰有一个 1」这种互斥关系，无法直接表达「这三格的数字之和等于 7」。所以工程上的正解是双层结构：

• 外层用 DLX 保证拉丁方合法性（硬约束）；
• 内层在每次落子后对受影响的 cage 做区间可行性剪枝（软约束），把不可能完成的分支提前砍掉。

这种「精确覆盖 + 约束传播」的组合，是精确覆盖类求解器最常见的扩展手法。同样的结构可以迁移到数织（Nonogram）、帐篷谜题等一大类逻辑谜题上。

三、cage 约束如何变成剪枝条件

设笼子剩余的未填格数为 k，剩余目标值为 t，已填部分为 S。对四种运算符分别有：

对于 + 和 ×，随着格子逐步填满，区间会急剧收窄，剪枝效果非常强；对于 −/÷，本质是两格配对约束，等价于在候选集里做交集过滤。

一个重要的工程细节：剪枝必须可增量恢复。DLX 在回溯时会撤销选择，cage 的已填状态也必须能随栈回滚，否则会出现状态污染。我的做法是把 cage 的「已填掩码 + 部分和 + 部分积」存成三元组，进入分支前保存旧值、回溯时还原。同样地，usedInRow/usedInCol 位图在「落子后立刻被剪枝拒绝」的分支上也必须复位——这是这类代码最容易漏掉的一行。

四、完整 Java 实现

4.1 数据结构

import java.util.*;

/** 肯肯的一个笼子：格子列表 + 目标值 + 运算符 */
final class Cage {
    final int target;
    final char op;              // '+', '-', '*', '/'
    final int[] cells;          // 展平后的格子下标 r*n+c
    int filledMask;             // 位掩码：哪些格子已填
    int sum;                    // 已填之和（op='+' 时使用）
    int prod;                   // 已填之积（op='*' 时使用）

    Cage(int target, char op, int[] cells) {
        this.target = target;
        this.op = op;
        this.cells = cells;
        this.prod = 1;
    }

    /** 保存现场，供回溯使用 */
    int[] save() { return new int[]{filledMask, sum, prod}; }

    /** 恢复现场 */
    void restore(int[] s) { filledMask = s[0]; sum = s[1]; prod = s[2]; }
}

4.2 DLX 核心

DLX 用数组模拟十字链表。L/R/U/D 存邻居下标，col[i] 存节点所属列头，rowId[i] 存节点来自哪一行（用于回溯出解）。列下标约定：0 为根；1..n² 为「格子已填」；其后两组各 n² 为「行-值」「列-值」。

/** 数组版 Dancing Links：插入整行、cover/uncover 均为 O(1) 指针操作 */
final class DLX {
    final int cols;
    final int[] L, R, U, D, col, rowId, size;
    int nodeCnt;

    DLX(int n) {
        this.cols = 3 * n * n;
        int maxNodes = cols + 1 + (n * n * n) * 3 + 8;   // 根 + 列头 + 每行 3 个节点
        L = new int[maxNodes]; R = new int[maxNodes];
        U = new int[maxNodes]; D = new int[maxNodes];
        col = new int[maxNodes]; rowId = new int[maxNodes];
        size = new int[cols + 1];
        nodeCnt = cols + 1;

        // 初始化列头横向环形链表
        for (int i = 0; i <= cols; i++) {
            L[i] = (i == 0) ? cols : i - 1;
            R[i] = (i == cols) ? 0 : i + 1;
            U[i] = D[i] = i;
            col[i] = i;
        }
    }

    /** 一次性添加一整行（候选三元组 r,c,v 的三个列号），保证水平链表正确 */
    void addRow(int row, int c1, int c2, int c3) {
        int[] cs = {c1, c2, c3};
        int first = -1, prev = -1;
        for (int c : cs) {
            int p = nodeCnt++;
            col[p] = c;
            rowId[p] = row;
            // 竖直方向插入到列尾
            U[p] = U[c]; D[p] = c;
            D[U[c]] = p; U[c] = p;
            size[c]++;
            // 水平方向拼接成环
            if (first == -1) {
                first = p; L[p] = p; R[p] = p;
            } else {
                R[prev] = p; L[p] = prev; R[p] = first; L[first] = p;
            }
            prev = p;
        }
    }

    /** 从列链表中摘除列 c 及其所有行 */
    void cover(int c) {
        R[L[c]] = R[c]; L[R[c]] = L[c];
        for (int i = D[c]; i != c; i = D[i]) {
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j]; D[U[j]] = D[j];
                size[col[j]]--;
            }
        }
    }

    /** 恢复列 c（严格逆序恢复，是 DLX 正确性的关键） */
    void uncover(int c) {
        for (int i = U[c]; i != c; i = U[i]) {
            for (int j = L[i]; j != i; j = L[j]) {
                U[D[j]] = j; D[U[j]] = j;
                size[col[j]]++;
            }
        }
        R[L[c]] = c; L[R[c]] = c;
    }
}

4.3 求解器：DLX + cage 剪枝

/** 肯肯求解器：Algorithm X 精确覆盖 + cage 区间可行性剪枝 */
public class KenKenSolver {
    final int n;
    final int[][] cellCage;        // 每格所属 cage 编号
    final int[][] cellIdxInCage;   // 每格在 cage 内的序号（用于位掩码）
    final Cage[] cages;
    final DLX dlx;
    final int[][] placements;      // 行号 -> {r, c, v, cageId, idxInCage}
    final boolean[][] usedInRow, usedInCol;   // 数值占用位图
    final int[] solution;          // solution[r*n+c] = v，0 表示空
    int nodesVisited = 0;

    public KenKenSolver(int n, int[][] cellCage, int[][] cellIdxInCage, Cage[] cages) {
        this.n = n; this.cellCage = cellCage; this.cellIdxInCage = cellIdxInCage;
        this.cages = cages;
        this.dlx = new DLX(n);
        this.solution = new int[n * n];
        this.usedInRow = new boolean[n][n + 1];
        this.usedInCol = new boolean[n][n + 1];

        int total = n * n * n;
        this.placements = new int[total][5];
        int base1 = 1, base2 = 1 + n * n, base3 = 1 + 2 * n * n;
        int rid = 0;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                for (int v = 1; v <= n; v++) {
                    placements[rid] = new int[]{r, c, v, cellCage[r][c], cellIdxInCage[r][c]};
                    // 三列：格子已填 / 行 r 已取 v / 列 c 已取 v
                    dlx.addRow(rid, base1 + r * n + c,
                                    base2 + r * n + (v - 1),
                                    base3 + c * n + (v - 1));
                    rid++;
                }
    }

    /** 深度优先搜索；返回 true 表示找到一个解 */
    boolean search() {
        nodesVisited++;
        if (dlx.R[0] == 0) return true;   // 所有列已恰好覆盖一次

        // 最小列优先：选节点最少的列，剪枝效果最好
        int bestC = -1, bestSize = Integer.MAX_VALUE;
        for (int c = dlx.R[0]; c != 0; c = dlx.R[c]) {
            if (dlx.size[c] < bestSize) { bestSize = dlx.size[c]; bestC = c; }
            if (bestSize == 0) return false;   // 该列无候选 -> 死路
        }

        dlx.cover(bestC);

        for (int i = dlx.D[bestC]; i != bestC; i = dlx.D[i]) {
            int row = dlx.rowId[i];
            int r = placements[row][0], c = placements[row][1], v = placements[row][2];
            int ci = placements[row][3];

            if (usedInRow[r][v] || usedInCol[c][v]) continue;   // 拉丁方冲突

            Cage cg = cages[ci];
            int[] snap = cg.save();
            solution[r * n + c] = v;              // 剪枝需要读到它，必须先写入

            if (!applyAndPrune(r, c, v, ci)) {
                // 关键：被剪枝拒绝的分支必须完整复位，包括两张占用表
                solution[r * n + c] = 0;
                usedInRow[r][v] = false;
                usedInCol[c][v] = false;
                cg.restore(snap);
                continue;
            }

            for (int j = dlx.R[i]; j != i; j = dlx.R[j]) dlx.cover(dlx.col[j]);

            if (search()) return true;

            // 回溯：严格逆序 uncover，再撤销落子
            for (int j = dlx.L[i]; j != i; j = dlx.L[j]) dlx.uncover(dlx.col[j]);
            solution[r * n + c] = 0;
            usedInRow[r][v] = false;
            usedInCol[c][v] = false;
            cg.restore(snap);
        }

        dlx.uncover(bestC);
        return false;
    }

    /** 落子并检查所属 cage 是否仍然可行 */
    boolean applyAndPrune(int r, int c, int v, int ci) {
        usedInRow[r][v] = true;
        usedInCol[c][v] = true;
        Cage cg = cages[ci];
        cg.filledMask |= (1 << cellIdxInCage[r][c]);
        if (cg.op == '+') {
            cg.sum += v;
            if (cg.sum > cg.target) return false;                 // 和已超额
        } else if (cg.op == '*') {
            cg.prod *= v;
            if (cg.prod > cg.target || cg.target % cg.prod != 0) return false;
        }
        return cageFeasible(cg);
    }

    /** cage 可行性判定：剩余格数 + 剩余目标值 */
    boolean cageFeasible(Cage cg) {
        int remaining = cg.cells.length - Integer.bitCount(cg.filledMask);

        if (remaining == 0) {                     // 全填满：精确校验
            if (cg.op == '+') return cg.sum == cg.target;
            if (cg.op == '*') return cg.prod == cg.target;
            int a = solution[cg.cells[0]], b = solution[cg.cells[1]];
            if (cg.op == '-') return Math.abs(a - b) == cg.target;
            return Math.max(a, b) % Math.min(a, b) == 0
                    && Math.max(a, b) / Math.min(a, b) == cg.target;
        }

        if (cg.op == '+') {
            int[] cand = freeValues(cg);
            if (cand.length == 0) return false;   // 无值可填
            return cg.sum + remaining * cand[0] <= cg.target
                    && cg.target <= cg.sum + remaining * cand[cand.length - 1];
        }

        if (cg.op == '*') {
            if (cg.target % cg.prod != 0) return false;
            return canFactor(cg.target / cg.prod, remaining);
        }

        if (remaining == 1) {                     // '-' 或 '/'：一格已定时另一格被唯一化
            int first = firstFilledValue(cg);
            if (first == 0) return true;
            if (cg.op == '-') {
                return (first - cg.target >= 1 && first - cg.target <= n)
                        || (first + cg.target >= 1 && first + cg.target <= n);
            }
            if (first % cg.target == 0 && first / cg.target >= 1) return true;
            return first * cg.target <= n;
        }
        return true;
    }

    /** 该 cage 内所有空格的可选值并集（升序） */
    int[] freeValues(Cage cg) {
        TreeSet<Integer> s = new TreeSet<>();
        for (int idx = 0; idx < cg.cells.length; idx++) {
            if ((cg.filledMask & (1 << idx)) != 0) continue;
            int cell = cg.cells[idx];
            int r = cell / n, c = cell % n;
            for (int v = 1; v <= n; v++)
                if (!usedInRow[r][v] && !usedInCol[c][v]) s.add(v);
        }
        return s.stream().mapToInt(Integer::intValue).toArray();
    }

    /** need 能否被分解为 k 个 1..n 的因子之积 */
    boolean canFactor(int need, int k) {
        if (k == 0) return need == 1;
        if (need == 1) return true;
        for (int f = 2; f <= Math.min(n, need); f++)
            if (need % f == 0 && canFactor(need / f, k - 1)) return true;
        return false;
    }

    int firstFilledValue(Cage cg) {
        for (int idx = 0; idx < cg.cells.length; idx++)
            if ((cg.filledMask & (1 << idx)) != 0) return solution[cg.cells[idx]];
        return 0;
    }

    public boolean solve() { return search(); }

    public void print() {
        for (int r = 0; r < n; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < n; c++) sb.append(solution[r * n + c]).append(' ');
            System.out.println(sb.toString().trim());
        }
        System.out.println("搜索节点数 = " + nodesVisited);
    }
}

4.4 跑一个 4×4 实例

这个实例经朴素枚举验证只有唯一解。

public class KenKenDemo {
    public static void main(String[] args) {
        int n = 4;

        // 每个 cage 的格子清单（行,列）
        int[][][] groups = {
            {{2, 1}, {2, 2}, {3, 1}},   // 0: 9×
            {{3, 2}, {3, 3}},            // 1: 2-
            {{0, 0}, {1, 0}},            // 2: 6×
            {{0, 2}, {0, 3}, {1, 2}},    // 3: 4×
            {{0, 1}, {1, 1}},            // 4: 2-
            {{2, 0}, {3, 0}},            // 5: 4÷
            {{1, 3}, {2, 3}}             // 6: 1-
        };
        int[] targets = {9, 2, 6, 4, 2, 4, 1};
        char[] ops    = {'*', '-', '*', '*', '-', '/', '-'};

        int[][] cageId = new int[n][n];
        int[][] idxIn  = new int[n][n];
        Cage[] cages = new Cage[groups.length];

        for (int i = 0; i < groups.length; i++) {
            int[] flat = new int[groups[i].length];
            for (int k = 0; k < groups[i].length; k++) {
                int r = groups[i][k][0], c = groups[i][k][1];
                cageId[r][c] = i;
                idxIn[r][c] = k;
                flat[k] = r * n + c;
            }
            cages[i] = new Cage(targets[i], ops[i], flat);
        }

        KenKenSolver solver = new KenKenSolver(n, cageId, idxIn, cages);
        if (solver.solve()) solver.print();
        else System.out.println("无解");
    }
}

编译运行（JDK 17+）：

$ javac KenKenDemo.java
$ java KenKenDemo
3 2 4 1
2 4 1 3
4 1 3 2
1 3 2 4
搜索节点数 = 38

38 个搜索节点意味着：DLX 的最小列优先策略几乎没走弯路——它一开始就盯住了「某行-值组合只剩一个候选」这样的强约束列，配合 cage 剪枝把大量拉丁方残局提前判死。

五、复杂度与工程结论

5.1 复杂度

• 空间：候选行 n³ 个、每行 3 个节点，共 3n³ 节点；列数 3n²。整体 O(n³)。
• 时间：精确覆盖是 NP 完全问题，最坏情况指数级。但最小列优先启发式在拉丁方类问题上通常把实际节点数压到很小——4×4 此例只需 38 个节点，9×9 数独的实测中位数在 10³ 量级。
• 剪枝开销：每落一子做一次 O(n·k) 的区间计算。它的价值在于把「已经注定失败的拉丁方」提前砍掉——尤其当 cage 很小（2~3 格）且目标值极端时（比如三格 3× 只能是 1,1,3 的一种排列），剪枝率最高。

5.2 两条容易踩的坑

1. 不要试图把 cage 约束塞进 0/1 矩阵。虽然理论上可以把每个 cage 的可行组合枚举成行，但组合数随笼子大小指数增长，矩阵会爆炸；把软约束放到剪枝层才是可持续的做法。
2. 剪枝状态必须可回滚。DLX 的 cover/uncover 是自洽的，而 cage 状态和 usedInRow/usedInCol 位图不是。缺少复位这一步，回溯后会残留脏状态，导致「明明有解却报无解」的隐性 bug——而且这种 bug 不抛异常，极难定位。

5.3 可以继续做的优化

• 候选值前向检查：在 freeValues 里再叠加「该值是否让本行/本列的某格无值可填」，即数独里的 naked single。
• Bitmask 化：把 usedInRow/usedInCol 合成 int 位掩码，取候选集用位运算，实测能再快 2~3 倍。
• 对称性破除：n×n 拉丁方存在大量对称解，若只求「任意一个解」，可把首行固定为 1..n 的顺序排列，搜索空间直接除以 n!。

六、小结

肯肯是一个非常适合练手的建模题：规则简单，但逼你回答两个真实问题——哪些约束能被精确覆盖表达，哪些不能，以及不能表达的那部分如何以可回滚的方式接进回溯。把这两件事做对，你就同时掌握了 DLX 的工程用法和约束传播的基本范式。