每日算法 — 使用java实现数独：唯一矩形与强制链的无猜测逻辑求解

一、为什么”能解出来”和”解得好”是两回事

大多数数独求解器只做一件事：回溯。给它一个 17 提示数的极限题，它能解出来，但你可能要等上几毫秒到几十毫秒，而且中间经历了几万次无效分支。

这套做法在工程上没问题，在教学上却有个隐患：它跳过了人类解题者真正的思考过程。人做数独时并不会”猜一个数然后祈祷”，而是用一系列可证明的推理逐步缩小候选数——直到某一步，题目被彻底解开，全程零猜测。

这篇要讲的就是这条路的顶点：唯一矩形（Unique Rectangle） 与 强制链（Forcing Chain）。前者利用”数独必须有唯一解”这个元约束做排除，后者把候选数之间的依赖关系建模成有向图，做传递闭包。两者都能把”需要猜测的题”变成”不需要猜测的题”。

二、解题工具箱的分层结构

一个完整的逻辑求解器应该按”代价从低到高”分层扫描，一旦某层有收获就回到最便宜的层重新开始：

L0~L4 已被大量文章覆盖，本文聚焦 L5 与 L6——这两层恰好是”从局部规则跃迁到全局推理”的分水岭。

三、唯一矩形：用”解的唯一性”当约束

3.1 核心洞察

假设四个格子构成一个矩形，分布在恰好两个行、两个列、两个宫里，且四格都只剩候选数 {a, b}：

  r1c1 {a,b}      r1c2 {a,b}
  r2c1 {a,b}      r2c2 {a,b}

如果这四格最终填成 a/b/b/a 与 b/a/a/b 的两种互换形式，那么交换 a 和 b 之后仍然是一个合法解。也就是说，若题目保证唯一解，这种”完全互换”的格局不可能出现在最终解中。

于是得到一个强推论：在这四格中，至少有一格必须填第三个数。若其中三格都是 {a,b}，第四格是 {a,b,c}，那么第四格必须填 c——直接确定。

这就是 Type-1 唯一矩形。它的杀伤力在于：结论来自”元信息”（题目唯一解），而不是棋盘上的局部约束。这是很多求解器从未实现的一层。

3.2 需要检测的几种形态

• Type 1：三格 {a,b}，第四格 {a,b,c} → 第四格 = c
• Type 2：两格 {a,b} 在对角（含额外候选 c），另两格 {a,b,c} → c 被限制在矩形所在的两个单元内，可对这两个单元做排除
• Type 4：某数在矩形某行/列内被”强链接”限制，可排除另一候选

工程上先实现 Type 1，已能解决相当比例的”困难”题；Type 2/4 需要更细的单元交集判定。

3.3 关键前置条件：矩形必须”跨宫正确”

这是最容易写错的地方。唯一矩形的成立要求四格所在的宫构成 2 个宫 × 2 格 的格局，即：

• 若两行在同一 band（同一组三行），则两列必须跨 band（不同 stack）；
• 否则两列可以在同一 stack。

如果四格全在一个宫里，交换 a/b 会同时破坏宫内约束以外的对称性——不成立。必须做这个几何校验，否则会把错误结论当定理用。

四、强制链：把候选数依赖建模成有向图

4.1 从”如果…则…”到图

人类解题时会说：”如果 r1c1 是 3，那么 r1 行里其他格不能是 3，于是 r1c5 只能是 7，于是 c5 列里 r9c5 不能是 7……”

这句话本质上是一条蕴含链：(r1c1=3) ⇒ (r1c5=7) ⇒ (r9c5≠7)。

把棋盘上每个”候选数” (格, 数字) 视为图的一个节点，把蕴含关系视为有向边，就得到候选图（candidate graph）。边只有两类：

1. 强链接（strong link）：某单元内数字 d 只有两个位置 p、q 时，p=d ⇒ q≠d 且 q=d ⇒ p≠d。这是双向边。
2. 弱链接（weak link）：某单元内 d 有 ≥2 个位置，任意两个之间是 p=d ⇒ q≠d（单向，但图上可视为有向）。

4.2 链的三种终止形态

• 矛盾链：从 X 出发，若沿链推出 X 的否定，则 X 为假，可删；
• 双向链（Nice Loop）：链回到起点，形成环，环上所有弱链接的端点可删 d；
• 异色链/XY-Chain：两个不同数字的链头尾相接，用”双值格”作为桥梁。

工程上最实用的简化版是 XY-Chain：只用双值格（恰好 2 个候选的格子）作为链节点，沿着”共享一个候选数”的关系游走，若链的首尾两格共享同一个候选 z，且链长 ≥ 3，则链外任何同时看到首尾两格且含 z 的格子可删 z。

这是可自动化的，且实现量不大。

五、项目结构

sudoku-logic/
├── pom.xml
└── src/main/java/com/dailyalgo/sudoku/
    ├── Grid.java          // 棋盘：候选位掩码 + 单元索引
    ├── Units.java         // 27 个单元（9 行 + 9 列 + 9 宫）
    ├── Technique.java     // 技巧接口：返回是否取得进展
    ├── Singles.java       // L0 + L1
    ├── LockedCandidates.java // L2
    ├── UniqueRectangle.java  // L5（本文重点）
    ├── ForcingChain.java     // L6（本文重点，XY-Chain 实现）
    ├── LogicSolver.java   // 分层调度器
    └── Main.java          // 演示 + 计时对比

六、核心代码

6.1 棋盘表示：位掩码

用 int 的低 9 位表示”候选数集合”，第 d 位为 1 表示 d 可填。所有排除操作退化为位运算 cand &= ~(1 << d)，极其高效。

package com.dailyalgo.sudoku;

/** 数独棋盘，候选数以位掩码存储（bit 0..8 对应数字 1..9） */
public class Grid {
    public static final int FULL = 0x1FF;   // 9 位全 1
    /** cells[r][c]：0 表示未填；否则为单个数字（1..9） */
    private final int[][] cells = new int[9][9];
    /** cand[r][c]：候选位掩码，仅当 cells[r][c] == 0 时有意义 */
    private final int[][] cand = new int[9][9];

    public Grid(int[][] puzzle) {
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                cells[r][c] = puzzle[r][c];
                cand[r][c] = puzzle[r][c] == 0 ? FULL : 0;
            }
        // 初始排除：已知数字约束其行/列/宫
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                if (cells[r][c] != 0) eliminateFromPeers(r, c, cells[r][c]);
    }

    public int value(int r, int c) { return cells[r][c]; }
    public int candidates(int r, int c) { return cells[r][c] == 0 ? cand[r][c] : 0; }
    public boolean isEmpty(int r, int c) { return cells[r][c] == 0; }

    /** 数字 d 在格 (r,c) 是否仍是候选 */
    public boolean hasCandidate(int r, int c, int d) {
        return isEmpty(r, c) && (cand[r][c] & (1 << (d - 1))) != 0;
    }

    public int candidateCount(int r, int c) {
        return Integer.bitCount(candidates(r, c));
    }

    /** 从 (r,c) 的同行/同列/同宫其他格中排除 d，返回是否真的删掉过 */
    public boolean eliminateFromPeers(int r, int c, int d) {
        boolean changed = false;
        int mask = ~(1 << (d - 1));
        for (int i = 0; i < 9; i++) {
            changed |= tryEliminate(r, i, mask);
            changed |= tryEliminate(i, c, mask);
        }
        int br = (r / 3) * 3, bc = (c / 3) * 3;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                changed |= tryEliminate(br + i, bc + j, mask);
        return changed;
    }

    /** 在单格上删除候选（不传播），返回是否删除成功 */
    public boolean tryEliminate(int r, int c, int mask) {
        if (!isEmpty(r, c)) return false;
        int before = cand[r][c];
        int after = before & mask;
        if (after == before) return false;
        if (after == 0) throw new IllegalStateException("格 (" + r + "," + c + ") 候选被清空，题面矛盾");
        cand[r][c] = after;
        return true;
    }

    /** 确定填数并传播 */
    public boolean assign(int r, int c, int d) {
        if (!isEmpty(r, c) || !hasCandidate(r, c, d)) return false;
        cells[r][c] = d;
        cand[r][c] = 0;
        eliminateFromPeers(r, c, d);
        return true;
    }

    public boolean isSolved() {
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                if (cells[r][c] == 0) return false;
        return true;
    }

    /** 深拷贝，用于假设推理 */
    public Grid copy() {
        Grid g = new Grid(new int[9][9]);
        for (int r = 0; r < 9; r++) {
            System.arraycopy(cells[r], 0, g.cells[r], 0, 9);
            System.arraycopy(cand[r], 0, g.cand[r], 0, 9);
        }
        return g;
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < 9; r++) {
            if (r % 3 == 0 && r != 0) sb.append("------+-------+------\n");
            for (int c = 0; c < 9; c++) {
                if (c % 3 == 0 && c != 0) sb.append("| ");
                sb.append(cells[r][c] == 0 ? "." : String.valueOf(cells[r][c])).append(' ');
            }
            sb.append('\n');
        }
        return sb.toString();
    }
}

6.2 唯一矩形（Type 1 与 Type 2）

注意 sharesTwoHouses 的几何校验——这是正确性的关键。

package com.dailyalgo.sudoku;

/**
 * 唯一矩形（Unique Rectangle）：
 * 依赖"题目有唯一解"这一元信息做排除。
 * 本类实现 Type-1（三格双值 → 第四格定型）与 Type-2（对角双值 → 第三数被限制在两单元内）。
 */
public class UniqueRectangle {

    /** 一次求解尝试的结果 */
    public record Result(boolean progressed, String reason) { }

    public Result apply(Grid g) {
        for (int r1 = 0; r1 < 8; r1++) {
            for (int r2 = r1 + 1; r2 < 9; r2++) {
                if (r2 - r1 == 0) continue;
                for (int c1 = 0; c1 < 8; c1++) {
                    for (int c2 = c1 + 1; c2 < 9; c2++) {
                        // 快速剪枝：四格必须都是双值格或"三值且含同一对"
                        int m11 = g.candidates(r1, c1), m12 = g.candidates(r1, c2);
                        int m21 = g.candidates(r2, c1), m22 = g.candidates(r2, c2);
                        if (m11 == 0 || m12 == 0 || m21 == 0 || m22 == 0) continue;
                        // 找出共同的两位候选组合
                        int pair = Integer.bitCount(m11) == 2 ? m11
                                 : Integer.bitCount(m12) == 2 ? m12
                                 : Integer.bitCount(m21) == 2 ? m21
                                 : Integer.bitCount(m22) == 2 ? m22 : 0;
                        if (pair == 0) continue;
                        if ((m11 & pair) != pair || (m12 & pair) != pair
                         || (m21 & pair) != pair || (m22 & pair) != pair) continue;
                        if (!sharesTwoHouses(r1, c1, r1, c2, r2, c1, r2, c2)) continue;

                        // 统计三格双值、一格多值的格局
                        int[][] cells = {{r1, c1}, {r1, c2}, {r2, c1}, {r2, c2}};
                        int multiIdx = -1, multiCount = 0;
                        for (int i = 0; i < 4; i++) {
                            int cnt = g.candidateCount(cells[i][0], cells[i][1]);
                            if (cnt > 2) { multiCount++; multiIdx = i; }
                        }

                        if (multiCount == 1) {
                            // Type-1：多值格必须填第三数
                            int extra = g.candidates(cells[multiIdx][0], cells[multiIdx][1]) & ~pair;
                            int third = Integer.numberOfTrailingZeros(extra) + 1;
                            int r = cells[multiIdx][0], c = cells[multiIdx][1];
                            if (third >= 1 && third <= 9 && g.assign(r, c, third)) {
                                return new Result(true,
                                    "唯一矩形Type-1：r" + (r + 1) + "c" + (c + 1) + " = " + third);
                            }
                        } else if (multiCount == 2) {
                            // Type-2：两个多值格必须共享同一个额外候选，且位于同一行/列
                            int i1 = -1, i2 = -1;
                            for (int i = 0; i < 4; i++) {
                                if (g.candidateCount(cells[i][0], cells[i][1]) > 2) {
                                    if (i1 < 0) i1 = i; else i2 = i;
                                }
                            }
                            int e1 = g.candidates(cells[i1][0], cells[i1][1]) & ~pair;
                            int e2 = g.candidates(cells[i2][0], cells[i2][1]) & ~pair;
                            int same = e1 & e2;
                            if (Integer.bitCount(same) != 1) continue;
                            int d = Integer.numberOfTrailingZeros(same) + 1;
                            // 额外候选必落在这两个格子所在的行/列内 → 该行/列其余格可排 d
                            int r = cells[i1][0] == cells[i2][0] ? cells[i1][0] : -1;
                            int c = (r == -1) ? cells[i1][1] : -1;
                            boolean changed = false;
                            if (r >= 0) {
                                for (int cc = 0; cc < 9; cc++) changed |= g.tryEliminate(r, cc, ~(1 << (d - 1)));
                            } else if (c >= 0) {
                                for (int rr = 0; rr < 9; rr++) changed |= g.tryEliminate(rr, c, ~(1 << (d - 1)));
                            }
                            if (changed) {
                                return new Result(true, "唯一矩形Type-2：排除 " + d + " 于 "
                                        + (r >= 0 ? ("行" + (r + 1)) : ("列" + (c + 1))));
                            }
                        }
                    }
                }
            }
        }
        return new Result(false, "");
    }

    /**
     * 几何校验：四格必须恰好分布在 2 行、2 列、2 宫（且宫的分布是 2×2 交错形态）。
     * 若四格全落在一个宫里，交换两候选会破坏对称性，唯一矩形不成立。
     */
    private boolean sharesTwoHouses(int r1, int c1, int r1b, int c2, int r2, int c1b, int r2b, int c2b) {
        int b1 = (r1 / 3) * 3 + (c1 / 3);
        int b2 = (r1b / 3) * 3 + (c2 / 3);
        int b3 = (r2 / 3) * 3 + (c1b / 3);
        int b4 = (r2b / 3) * 3 + (c2b / 3);
        // 必须是 2 个不同的宫，每宫各 2 格
        // 情形 A：r1,r2 在同一 band → 则 c1,c2 必须不同 stack
        int band1 = r1 / 3, band2 = r2b / 3;
        int stack1 = c1 / 3, stack2 = c2b / 3;
        if (band1 == band2 && stack1 == stack2) return false;   // 全在一个宫里
        // 对角格必须同宫（Type 要求），且另外对角格也同宫
        return (b1 == b4 && b2 == b3 && b1 != b2) || (b1 == b2 && b3 == b4 && b1 != b3);
    }
}

6.3 强制链（XY-Chain 形式）

把双值格当作图中的节点，两格”共享某一候选”即存在边。找出首尾共享候选 z 的链，做链外排除。

package com.dailyalgo.sudoku;

import java.util.*;

/**
 * XY-Chain（强制链的一种可自动化形式）。
 *
 * 图模型：
 *   节点 = 双值格 (r,c)，标签为其两个候选 {x,y}
 *   边   = 两格共享至少一个候选（即"看见"彼此，同单元）
 * 链搜索：
 *   从格 A 出发，沿"共享候选"逐跳前进，每跳的进入候选必须与离开候选不同；
 *   若最终到达格 B 且 A、B 共享候选 z，则任何同时看见 A、B 的格可排除 z。
 *
 * 链长上限设为 6 跳，兼顾可行性与收益。
 */
public class ForcingChain {

    public record Result(boolean progressed, String reason) { }

    private static final int MAX_HOPS = 6;

    public Result apply(Grid g) {
        int[][] bival = collectBivalue(g);
        int n = bival.length;
        if (n < 3) return new Result(false, "");

        // 邻接关系：两格是否同单元（"看见"）
        boolean[][] see = new boolean[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                see[i][j] = see[j][i] = peers(bival, i, j);

        // 对所有起点做 DFS，记录路径上的格子序列
        for (int s = 0; s < n; s++) {
            List<Integer> path = new ArrayList<>();
            path.add(s);
            Result r = dfs(g, bival, see, s, s, -1, path);
            if (r.progressed()) return r;
        }
        return new Result(false, "");
    }

    /**
     * @param start 链首格索引
     * @param cur   当前格索引
     * @param inCandidate 进入当前格时所用的候选数（首次为 -1）
     */
    private Result dfs(Grid g, int[][] bival, boolean[][] see,
                       int start, int cur, int inCandidate, List<Integer> path) {
        if (path.size() >= 3) {
            int z = sharedCandidate(g, bival, start, cur);
            // 首尾必须共享候选，且该候选与链端的进出候选一致
            if (z != 0 && z != inCandidate) {
                Result r = eliminateOutside(g, bival, path, start, cur, z);
                if (r.progressed()) return r;
            }
        }
        if (path.size() >= MAX_HOPS) return new Result(false, "");

        int outCandidate = outCandidateOf(g, bival, cur, inCandidate);
        if (outCandidate == 0) return new Result(false, "");

        for (int nxt = 0; nxt < bival.length; nxt++) {
            if (path.contains(nxt)) continue;
            if (!see[cur][nxt]) continue;
            if (!containsCandidate(g, bival, nxt, outCandidate)) continue;
            path.add(nxt);
            Result r = dfs(g, bival, see, start, nxt, outCandidate, path);
            if (r.progressed()) return r;
            path.remove(path.size() - 1);
        }
        return new Result(false, "");
    }

    /** 链首尾共享的候选（必须唯一，否则语义含糊） */
    private int sharedCandidate(Grid g, int[][] bival, int a, int b) {
        int ma = g.candidates(bival[a][0], bival[a][1]);
        int mb = g.candidates(bival[b][0], bival[b][1]);
        int both = ma & mb;
        return Integer.bitCount(both) == 1 ? Integer.numberOfTrailingZeros(both) + 1 : 0;
    }

    /** 以 inCandidate 进入后，离开该格时使用的候选（另一候选） */
    private int outCandidateOf(Grid g, int[][] bival, int idx, int inCandidate) {
        int m = g.candidates(bival[idx][0], bival[idx][1]);
        int other = m & ~(1 << (inCandidate - 1));
        if (Integer.bitCount(other) != 1) return 0;
        return Integer.numberOfTrailingZeros(other) + 1;
    }

    private boolean containsCandidate(Grid g, int[][] bival, int idx, int d) {
        return (g.candidates(bival[idx][0], bival[idx][1]) & (1 << (d - 1))) != 0;
    }

    /** 链外排除：任何同时看见链首、链尾且含 z 的格，删掉 z */
    private Result eliminateOutside(Grid g, int[][] bival, List<Integer> path,
                                    int start, int end, int z) {
        int r1 = bival[start][0], c1 = bival[start][1];
        int r2 = bival[end][0], c2 = bival[end][1];
        boolean changed = false;
        String witness = null;
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (pathCellsContain(bival, path, r, c)) continue;
                if (!g.hasCandidate(r, c, z)) continue;
                if (peersOf(r1, c1, r, c) && peersOf(r2, c2, r, c)) {
                    g.tryEliminate(r, c, ~(1 << (z - 1)));
                    changed = true;
                    if (witness == null) witness = "r" + (r + 1) + "c" + (c + 1);
                }
            }
        }
        return changed ? new Result(true, "XY-Chain 长" + path.size() + "：在 " + witness + " 排除 " + z)
                       : new Result(false, "");
    }

    private boolean pathCellsContain(int[][] bival, List<Integer> path, int r, int c) {
        for (int idx : path) if (bival[idx][0] == r && bival[idx][1] == c) return true;
        return false;
    }

    private boolean peersOf(int r1, int c1, int r2, int c2) {
        return r1 == r2 || c1 == c2
            || (r1 / 3 == r2 / 3 && c1 / 3 == c2 / 3);
    }

    private boolean peers(int[][] bival, int i, int j) {
        return peersOf(bival[i][0], bival[i][1], bival[j][0], bival[j][1]);
    }

    private int[][] collectBivalue(Grid g) {
        List<int[]> list = new ArrayList<>();
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                if (g.candidateCount(r, c) == 2) list.add(new int[]{r, c});
        return list.toArray(new int[0][]);
    }
}

6.4 分层调度器

package com.dailyalgo.sudoku;

/** 按代价从低到高分层的逻辑求解器 */
public class LogicSolver {

    private final Grid g;
    private int urUsed, chainUsed;

    public LogicSolver(Grid g) { this.g = g; }

    public boolean solve() {
        int guard = 0;
        while (!g.isSolved()) {
            if (++guard > 2000) return false;          // 防止死循环
            if (singles()) continue;                    // L0 + L1
            if (lockedCandidates()) continue;           // L2
            UniqueRectangle.Result ur = new UniqueRectangle().apply(g);
            if (ur.progressed()) { urUsed++; log(ur.reason()); continue; }
            ForcingChain.Result fc = new ForcingChain().apply(g);
            if (fc.progressed()) { chainUsed++; log(fc.reason()); continue; }
            return false;                               // 逻辑卡住，需要回溯兜底
        }
        return true;
    }

    public int uniqueRectangleUses() { return urUsed; }
    public int forcingChainUses() { return chainUsed; }

    private void log(String msg) { System.out.println("  → " + msg); }

    /** 唯一候选 + 隐性唯一 */
    private boolean singles() {
        boolean changed = false;
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++) {
                if (!g.isEmpty(r, c)) continue;
                int m = g.candidates(r, c);
                if (Integer.bitCount(m) == 1) {
                    int d = Integer.numberOfTrailingZeros(m) + 1;
                    g.assign(r, c, d);
                    changed = true;
                }
            }
        // 隐性唯一：某数字在某单元只剩一个位置
        for (int d = 1; d <= 9; d++) {
            for (int r = 0; r < 9; r++) {
                int pos = -1, count = 0;
                for (int c = 0; c < 9; c++)
                    if (g.hasCandidate(r, c, d)) { pos = c; count++; }
                if (count == 1 && g.isEmpty(r, pos)) { g.assign(r, pos, d); changed = true; }
            }
            for (int c = 0; c < 9; c++) {
                int pos = -1, count = 0;
                for (int r = 0; r < 9; r++)
                    if (g.hasCandidate(r, c, d)) { pos = r; count++; }
                if (count == 1 && g.isEmpty(pos, c)) { g.assign(pos, c, d); changed = true; }
            }
        }
        return changed;
    }

    /** 锁定候选（Pointing / Claiming） */
    private boolean lockedCandidates() {
        boolean changed = false;
        for (int d = 1; d <= 9; d++) {
            // Pointing：宫内某数字被限制在同一行/列 → 排除该行/列其他格
            for (int br = 0; br < 3; br++) {
                for (int bc = 0; bc < 3; bc++) {
                    int sameRow = -1, sameCol = -1, cnt = 0;
                    for (int i = 0; i < 3; i++)
                        for (int j = 0; j < 3; j++) {
                            int r = br * 3 + i, c = bc * 3 + j;
                            if (g.hasCandidate(r, c, d)) {
                                cnt++;
                                if (sameRow == -1) sameRow = r;
                                else if (sameRow != r) sameRow = -2;
                                if (sameCol == -1) sameCol = c;
                                else if (sameCol != c) sameCol = -2;
                            }
                        }
                    if (cnt == 0 || cnt > 3) continue;
                    if (sameRow >= 0) {
                        for (int c = 0; c < 9; c++)
                            if (c / 3 != bc) changed |= g.tryEliminate(sameRow, c, ~(1 << (d - 1)));
                    }
                    if (sameCol >= 0) {
                        for (int r = 0; r < 9; r++)
                            if (r / 3 != br) changed |= g.tryEliminate(r, sameCol, ~(1 << (d - 1)));
                    }
                }
            }
        }
        return changed;
    }
}

6.5 演示入口

package com.dailyalgo.sudoku;

public class Main {
    public static void main(String[] args) {
        // 一道需要高级逻辑的题目（唯一矩形与 XY-Chain 均可命中）
        int[][] puzzle = {
            {0, 0, 0, 2, 6, 0, 7, 0, 1},
            {6, 8, 0, 0, 7, 0, 0, 9, 0},
            {1, 9, 0, 0, 0, 4, 5, 0, 0},
            {8, 2, 0, 1, 0, 0, 0, 4, 0},
            {0, 0, 4, 6, 0, 2, 9, 0, 0},
            {0, 5, 0, 0, 0, 3, 0, 2, 8},
            {0, 0, 9, 3, 0, 0, 0, 7, 4},
            {0, 4, 0, 0, 5, 0, 0, 3, 6},
            {7, 0, 3, 0, 1, 8, 0, 0, 0}
        };

        Grid grid = new Grid(puzzle);
        System.out.println("初始盘面：\n" + grid);

        long t0 = System.nanoTime();
        LogicSolver solver = new LogicSolver(grid);
        boolean ok = solver.solve();
        long t1 = System.nanoTime();

        System.out.println("求解结果：\n" + grid);
        System.out.printf("成功=%s  耗时=%.3f ms  唯一矩形使用=%d 次  强制链使用=%d 次%n",
                ok, (t1 - t0) / 1e6, solver.uniqueRectangleUses(), solver.forcingChainUses());

        if (!ok) {
            System.out.println("纯逻辑未能完成，交由回溯兜底（此处从略）");
        }
    }
}

七、一件值得单独说的事：为什么”唯一矩形”是合法推理

初学者最常质疑的是这一点：凭什么可以用”题目有唯一解”这个前提？

答案是前提集合不同。数独规则本身（行列宫不重复）不足以推出唯一矩形结论；一旦加上”题目由合格出题者提供，保证唯一解”这一元约束，结论就在这套公理系统中可证。这与程序验证中”假设输入满足前置条件”完全同构。

副作用也很明确：如果题目确实有多解，唯一矩形会给出错误结论。工程实践中的防御手段是——用唯一矩形推出结论后，不立即传播到终局，而是先记下该推理，最终用回溯验证得到的解是否唯一。本文代码为教学目的省略了这一步，生产环境请补上。

八、性能观察

在一组 100 道”困难”级题目上的实测（单核 Java 17）：

注意这里的耗时下降不是因为单次操作更快，而是因为需要进入回溯的题目变少了。回溯的代价是分支数的指数级爆炸，而逻辑推理是多项式开销——省掉一次回溯，往往抵得上几百次排除。

九、小结

数独这类”规则极简、状态空间巨大”的谜题，最有意思的地方在于：它的难度不来自搜索规模，而来自推理深度。唯一矩形展示了”元约束”的力量，强制链展示了”把蕴含关系图化”的力量。这两条思路都能平移到其他领域：

• 唯一矩形 → 在约束满足问题中，利用”解集基数”作为额外约束做剪枝；
• 强制链 → 把”若 A 则 B”的依赖显式建成有向图，用传递闭包做全局排除，而不是逐条规则匹配。

代码可直接运行，Grid 的位掩码设计也让后续接入更多技法（ALS、W-Wing、Almost Locked Set）变得非常容易。