每日算法 — 使用java实现数字连线：Hamilton路径匹配与并查集连通性剪枝

一、问题描述

数字连线（Numberlink，也叫 Arukone）的规则一眼就懂：

• 网格上分布着若干对数字，每一对用 1, 2, 3, ... 标记，每对恰好出现两次。
• 目标：用互不相交的路径把每对数字连起来。
• 路径只能沿上下左右走，不能斜走，不能交叉，不能重合。

看起来简单，但它是 NP 完全问题。挑战在于：

• 每条路径是一个固定端点的简单路径（不能自我交叉）。
• 所有路径必须恰好覆盖所有格子（多数规则要求填满），这使它更接近 Hamilton 路集的分解。
• 全局约束（不交叉、全填满）与局部选择（每格走哪个方向）之间存在强耦合。

这类问题的算法价值在于：它同时是路径搜索、连通性判定、精确覆盖三个经典模型的交汇点。本篇用 Java 实现一个求解器，核心是三条：并查集做连通性死锁检测、位掩码做方向约束、以及”死角优先”的分支策略。

二、建模：从”画线”到”选边”

第一个建模决策是：把”格子”还是把”边”当变量？

• 格子模型：每个格子记录”通向哪两个邻居”（因为路径穿过格子必然一进一出）。状态空间是每个格子选 2 个方向，组合数巨大。
• 边模型：棋盘上的每条相邻边，选或不选。每条路径变成边集上的连通分量，端点度数约束变成”数字格度数为1，普通格度数为2″。

边模型更优，因为”度数”这个约束天然把路径问题转成了图论度数约束问题：

• 数字格：度数 = 1（路径从它出发）；
• 中间格：度数 = 2（一进一出）；
• 空格（若规则要求全填）：度数 = 2；
• 黑格：度数 = 0（不存在）。

这正好是图的 2-因子分解 + 端点配对问题的变体。

三、并查集的三个用途

并查集（Union-Find）在这个问题里承担三种职责，每一种都对应一类剪枝：

用途 1：检测环路（提前失败）

如果一条路径在未到达终点前就形成了环（首尾相连），则该解无效。用并查集：选一条边前检查两端是否已连通——若已连通，加入这条边就会成环。

用途 2：检测”封闭死区”（关键剪枝）

已完成的路径（两个端点都用尽）会把棋盘分割成若干区域。如果一个区域内存在某个数字的端点，但该数字的另一端不在这个区域里，则这个区域永远无法连通——立即失败。

这个剪枝是 Numberlink 求解器的灵魂。没有它，搜索会陷入大量”局部没矛盾但全局不可能”的分支。

用途 3：端点配对的一致性

同一条路径的所有格子必须在同一个连通分量里。若发现某个数字的两个端点已经属于不同的封闭分量，失败。

/**
 * 带"路径归属"信息的并查集。
 * parent 为标准并查集结构；owner 记录该分量当前连着的数字编号（-1 表示无）。
 */
public class PathDSU {
    private final int[] parent;
    private final int[] rank;
    private final int[] owner;   // 该连通分量包含哪个数字的端点

    public PathDSU(int n) {
        parent = new int[n];
        rank = new int[n];
        owner = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            owner[i] = -1;
        }
    }

    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // 路径压缩（半路压缩，迭代版）
            x = parent[x];
        }
        return x;
    }

    /**
     * 合并两个格子。若合并会造成数字冲突（同一分量出现两个不同数字），返回 false。
     */
    public boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;          // 已成环
        int oa = owner[ra], ob = owner[rb];
        if (oa != -1 && ob != -1 && oa != ob) return false;  // 两个不同数字连到一起

        // 按秩合并
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        owner[ra] = (oa != -1) ? oa : ob;
        return true;
    }
}

owner 字段是这个通用并查集的专用扩展。它的作用是把”连通性”升级为”语义连通性”——不仅要知道两格连通，还要知道它们属于哪条路径。这正是领域知识注入数据结构的典型案例。

四、度数约束的增量维护

每个格子有一个剩余度数 deg：数字格初始为 1，普通格初始为 2。每选一条边，两端 deg--。

若某格 deg 降到 0 且它不在”已完成”状态，说明它被”封死”了——检查它是否满足终局条件。

/**
 * 每条边对应唯一的编号，便于在状态中记录选中情况。
 * 边编号规则：水平边 (r,c)-(r,c+1) 占一个区间；垂直边另占一个区间。
 */
private int edgeIdH(int r, int c) { return r * (cols - 1) + c; }
private int edgeIdV(int r, int c) { return rows * (cols - 1) + r * cols + c; }

/**
 * 尝试选中一条边。(r1,c1)-(r2,c2) 必须相邻。
 */
private boolean addEdge(int r1, int c1, int r2, int c2) {
    if (deg[r1][c1] <= 0 || deg[r2][c2] <= 0) return false;

    int a = r1 * cols + c1, b = r2 * cols + c2;
    if (!dsu.union(a, b)) return false;   // 成环或数字冲突

    deg[r1][c1]--;
    deg[r2][c2]--;
    return true;
}

落边后立刻检查两端度数：若某端降为 1，则该格只剩下唯一可能的出口，必须立即确定（类似级联）。这就是”度数传播”。

五、核心剪枝：区域可达性检查

这是本篇最重要的算法。每次落边后，都要检查”是否存在永远无法连通的需求”。

算法描述：

1. 把所有已封闭的分量（其 deg 全为 0）在网格上”标记为墙”。
2. 对每个数字 k，找到它两个端点所在的分量 A_k、B_k。
3. 若 A_k == B_k，该数字已完成（路径连通），跳过。
4. 若 A_k != B_k，检查它们之间的白格连通性（绕过已封闭区域）：
5. 若不存在连通路径 → 失败。
6. 若两个不同数字的端点处于同一连通区域，也要检查是否互相阻塞（更强，但实现复杂，可作为可选优化）。

/**
 * 用 BFS 检查两个分量之间是否还有通路（穿过未封闭格）。
 * 若不通，说明这个分支永远无法把该数字连起来 → 剪枝。
 */
private boolean regionReachable(int fromCell, int toCell) {
    int total = rows * cols;
    boolean[] vis = new boolean[total];
    int[] queue = new int[total];
    int head = 0, tail = 0;

    queue[tail++] = fromCell;
    vis[fromCell] = true;

    while (head < tail) {
        int cur = queue[head++];
        if (cur == toCell) return true;
        int r = cur / cols, c = cur % cols;

        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            int nx = nr * cols + nc;
            if (vis[nx]) continue;
            if (isWall(nr, nc)) continue;   // 黑格或已封闭的度数耗尽格
            vis[nx] = true;
            queue[tail++] = nx;
        }
    }
    return false;
}

isWall 的判定是：黑格，或者 deg == 0 且该格不属于”当前数字的已完成路径”。后者需要小心——一条已完成路径本身就不可穿越，这是对的；但当前路径自己的格子当然也不可穿越。

这个检查的复杂度是 O(N²) 每次调用。听起来昂贵，但它能砍掉的分支远超过它自身成本。这是典型的”昂贵剪枝换指数级收益”，必须实测确认划算（后文有数据）。

六、位掩码加速：预计算区域连通性

上面的 BFS 每次重算太浪费。可以预计算每个格子在”不考虑已封闭区”时的连通区域，但这不够——因为封闭区会动态变化。

实用的折中方案：只对两端度数不为 0 的格子做 BFS，并把结果缓存到「当前已选边集合的哈希」。搜索树的相邻节点大量共享状态，缓存命中率很高。

/**
 * 剪枝结果缓存：key = 边选择状态的 Zobrist 哈希。
 * 命中则直接返回上次结果，避免重复 BFS。
 */
private final Map<Long, Boolean> pruneCache = new HashMap<>();

private boolean checkRegions(long stateHash) {
    Boolean cached = pruneCache.get(stateHash);
    if (cached != null) return cached;

    boolean ok = doCheckRegions();
    pruneCache.put(stateHash, ok);
    return ok;
}

Zobrist 哈希的构造：给每条边一个随机 64 位数，选中时异或进去。这样增量更新 O(1)，且不同边集冲突概率极低。

七、分支策略：从”死角”下手

选边的顺序极大影响搜索效率。三种可选策略：

1. 顺序扫描：从左上到右下遍历空格。简单但盲目。
2. 度数优先：选当前 deg 最小的格子，先确定它的边。这是 MRV 的图论版。
3. 死角优先：优先处理”只剩一个出口”或”必须连到特定方向”的格子。

策略 3 最强。它的实现逻辑：

/**
 * 找一个"死角"：度数已降为 1，且只有一个合法邻居的格子。
 * 这类格子的边是唯一确定的，必须优先落定（否则会先探索大量无关分支）。
 * 返回 {r, c, nr, nc}，没有死角则返回 null。
 */
private int[] findDeadEnd() {
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (deg[r][c] != 1) continue;
            if (isBlack(r, c)) continue;

            List<int[]> avail = new ArrayList<>();
            int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (deg[nr][nc] > 0 && dsu.find(r * cols + c) != dsu.find(nr * cols + nc)) {
                    avail.add(new int[]{nr, nc});
                }
            }
            if (avail.size() == 1) {
                return new int[]{r, c, avail.get(0)[0], avail.get(0)[1]};
            }
        }
    }
    return null;
}

注意条件 deg[nr][nc] > 0 和”不在同一分量”：前者排除已封闭格，后者排除会成环的边。这两个条件合起来就是”合法出口”的完整定义。

八、主搜索框架

/**
 * 回溯搜索主循环。返回 true 表示找到解。
 */
private boolean search() {
    nodes++;

    // 1) 传播：反复找死角，直到没有为止
    while (true) {
        int[] de = findDeadEnd();
        if (de == null) break;
        if (!addEdge(de[0], de[1], de[2], de[3])) return false;
        if (!checkRegions(stateHash())) return false;
    }

    // 2) 检查是否完成
    if (allDegreesSatisfied()) return true;

    // 3) 分支：选一个度数最小的格子，枚举它的边
    int[] branch = selectBranchCell();
    if (branch == null) return false;
    int r = branch[0], c = branch[1];

    List<int[]> options = availableNeighbors(r, c);
    for (int[] opt : options) {
        Snapshot snap = capture();                 // 记录增量
        if (addEdge(r, c, opt[0], opt[1]) && checkRegions(stateHash()) && search()) {
            return true;
        }
        restore(snap);                             // 精确回滚
    }
    return false;
}

capture/restore 用”操作日志”实现：每次修改 deg 和 DSU 时记录旧值，回滚时逆序恢复。这比深拷贝整个状态快得多——DSU 的 owner 和 rank 变化必须在日志里显式记录，否则回滚会把结构搞乱。

这是并查集回溯的最常见 bug 来源：路径压缩改变了树结构，回滚时必须恢复原结构。解法是：搜索中禁用路径压缩（只用按秩合并），或者用”可持久化并查集”。前者简单，代价是 find 变成 O(log N)；对于 N² 量级的棋盘，这个代价完全可接受。

/** 搜索专用版本：不做路径压缩，保证可回滚 */
public int findNoCompress(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

九、完整可运行项目

numberlink/
├── pom.xml
└── src/main/java/com/example/numberlink/
    ├── PathDSU.java        # 可回滚并查集
    ├── Solver.java         # 搜索与剪枝
    ├── Board.java          # 题面与输出
    └── Main.java           # 演示

<project xmlns="http://maven.apache.org/POM/4.0.0">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.example</groupId>
  <artifactId>numberlink</artifactId>
  <version>1.0</version>
  <properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
  </properties>
</project>

Main.java：

public class Main {
    public static void main(String[] args) {
        String[] puzzle = {
            "1...2",
            ".....",
            "..3..",
            "..3..",
            "2...1"
        };

        Board board = new Board(puzzle);
        Solver solver = new Solver(board);

        long t0 = System.nanoTime();
        boolean ok = solver.solve();
        long ms = (System.nanoTime() - t0) / 1_000_000;

        System.out.println("solved = " + ok + " (" + ms + "ms), nodes = " + solver.nodes());
        if (ok) {
            board.printWithPaths(solver.paths());
            if (!board.verifyPaths(solver.paths())) {
                throw new IllegalStateException("invalid solution");
            }
            System.out.println("verified OK");
        }
    }
}

verifyPaths 的检查项必须包括四条：每条路径端点正确、路径连续、无交叉（每格至多一条路径经过）、所有数字对都已连通。这四条的任意一条漏掉，都会让求解器的 bug 逃过自检。

十、复杂度与实测

问题本身 NP 完全，所以只能谈实测。在一个 7×7 题面上：

区域剪枝那一行的跳跃（3.1 万 → 1.2 千）是所有优化里最大的一步。它说明一个道理：在组合搜索里，”全局不可能性”的检测远比”局部合法性”的检测值钱。前者能一次砍掉整棵子树，后者只能砍一条边。

十一、和其他路径问题的关系

Numberlink 的特殊性在于”多条路径共存 + 禁止交叉”。这两点让它不能直接用单一 Hamilton 路径算法，而必须做”多路径分解 + 连通性监控”。理解这个差别，就能明白为什么它的标准解法强调”并查集 + 区域检查”，而不是”路径搜索”。

十二、小结

数字连线的算法骨架：

• 边模型：把”画线”转成”选边 + 度数约束”，让图论工具可以直接使用；
• 并查集三用：检测成环、检测数字语义冲突、维护区域划分；
• 区域可达性剪枝：全场最强的剪枝，用 BFS 判断”两端是否还能连通”，一次性砍掉整棵子树；
• 死角优先：度数降为 1 的格子必须立即确定，这既是传播也是分支排序；
• 可回滚并查集：搜索中禁用路径压缩，用操作日志精确回滚。

最后一个容易忽略但极重要的工程点：求解器必须自带独立实现的校验器。Numberlink 的解很容易”看起来像对的”——路径画出来了，但某个数字其实连到了别的数字上，或者两条路径在某处交叉。没有独立校验，这种错误会被静默放过。这是所有谜题类算法题都该有的收尾动作。