每日算法 — 使用java实现数回：回路约束传播与并查集连通检测

一、游戏背景与规则

数回（Slitherlink / 回线拼图）是日本 Nikoli 出版社推出的经典逻辑解谜游戏。游戏规则简洁而深邃：在一个由点构成的矩形网格中，玩家需要在部分点之间画线，形成一条唯一的闭合回路。网格中某些格子内标注了数字（0-3），表示该格子四条边上实线的数量。

例如，数字”3″表示该格子的四条边中恰好有三条是回路的一部分；数字”0″表示四条边都不能有线。没有数字的格子则没有任何限制。最终，所有实线必须连接成一条且仅一条没有分叉、没有断点的闭合回路。

本文将用Java实现一个数回求解器，核心算法结合约束传播（Constraint Propagation）与并查集（Union-Find）连通性检测，高效缩小搜索空间后通过回溯法完成求解。

二、核心算法原理

2.1 网格表示

对于一个 M×N 的点阵，水平边有 M×(N-1) 条，垂直边有 (M-1)×N 条。用两个二维数组分别表示：
– hEdges[M][N-1]：水平边，0=未确定，1=有线，-1=无钱
– vEdges[M-1][N]：垂直边，同理

数字约束在 M-1 × N-1 的格子上。

2.2 约束传播

约束传播是求解数回的核心效率手段。基本规则包括：
– 数字0：四条边全部标记为无钱
– 数字3：三条边为有线，一条为无钱。若已知某边无钱，则其余三条必有线
– 数字2：四条边中恰好两条有线，多种组合可能
– 数字1：恰好一条有线
– 顶点约束：每个顶点最多两条边相连（回路无分叉）
– 短回路预防：除最终解外，不允许形成小闭合回路

2.3 并查集连通检测

随着边的确定，需要确保：
1. 已确定的线段不会过早形成闭合小回路（除非所有约束已满足且所有边已确定）
2. 最终所有线段属于同一个连通分量

并查集维护每个”线段端点”的连通性。当添加一条新边时，检查其两个端点是否已在同一集合：若是，则形成回路；若此时还有未确定的边，则此操作非法（会形成多个回路）。

三、Java实现

3.1 网格表示与基础操作

import java.util.*;

/**
 * 数回（Slitherlink）求解器
 * 约束传播 + 并查集 + 回溯法
 */
public class SlitherlinkSolver {

    private int rows; // 点数行数
    private int cols; // 点数列数
    private int[][] numbers; // 数字约束 grid[rows-1][cols-1], -1表示无数字

    // 边状态: 0=未确定, 1=有线, -1=无钱
    private int[][] hEdges; // 水平边 [rows][cols-1]
    private int[][] vEdges; // 垂直边 [rows-1][cols]

    // 并查集用于连通性检测
    private int[] parent;
    private int[] rank;

    public SlitherlinkSolver(int[][] numbers) {
        this.rows = numbers.length + 1;
        this.cols = numbers[0].length + 1;
        this.numbers = numbers;
        this.hEdges = new int[rows][cols - 1];
        this.vEdges = new int[rows - 1][cols];
    }

    /**
     * 将点坐标(r,c)映射为并查集的一维索引
     */
    private int pointId(int r, int c) {
        return r * cols + c;
    }

    /**
     * 初始化并查集
     */
    private void initUnionFind() {
        int n = rows * cols;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    private boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // 已在同一集合
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }

    /**
     * 获取某格子四条边的状态 [上,下,左,右]，1=有线,-1=无钱,0=未确定
     */
    private int[] getCellEdges(int r, int c) {
        return new int[]{
            hEdges[r][c],       // 上边
            hEdges[r + 1][c],   // 下边
            vEdges[r][c],       // 左边
            vEdges[r][c + 1]    // 右边
        };
    }

    /**
     * 设置水平边状态
     */
    private void setHEdge(int r, int c, int state) {
        hEdges[r][c] = state;
    }

    /**
     * 设置垂直边状态
     */
    private void setVEdge(int r, int c, int state) {
        vEdges[r][c] = state;
    }

    /**
     * 统计某格子已确定的有线/无钱边数量
     */
    private int[] countCellEdges(int r, int c) {
        int[] edges = getCellEdges(r, c);
        int on = 0, off = 0;
        for (int e : edges) {
            if (e == 1) on++;
            else if (e == -1) off++;
        }
        return new int[]{on, off};
    }

3.2 约束传播引擎

    /**
     * 约束传播主函数：循环应用所有规则直到无法继续推导
     * @return true表示当前状态一致（无矛盾），false表示出现矛盾
     */
    public boolean propagate() {
        boolean changed = true;
        while (changed) {
            changed = false;

            // 规则1：数字约束传播
            for (int r = 0; r < rows - 1; r++) {
                for (int c = 0; c < cols - 1; c++) {
                    if (numbers[r][c] < 0) continue;
                    int num = numbers[r][c];
                    int[] counts = countCellEdges(r, c);
                    int on = counts[0], off = counts[1];
                    int[] edges = getCellEdges(r, c);

                    // 若已有线数+未确定数 == 目标，则未确定的全设为有线
                    if (on + (4 - on - off) == num) {
                        for (int i = 0; i < 4; i++) {
                            if (edges[i] == 0) {
                                if (!setEdgeByCellDir(r, c, i, 1)) return false;
                                changed = true;
                            }
                        }
                    }
                    // 若已有线数 == 目标，则未确定的全设为无钱
                    if (on == num) {
                        for (int i = 0; i < 4; i++) {
                            if (edges[i] == 0) {
                                if (!setEdgeByCellDir(r, c, i, -1)) return false;
                                changed = true;
                            }
                        }
                    }
                    // 若已有线数 > 目标 或 已有线数+未确定数 < 目标，矛盾
                    if (on > num || on + (4 - on - off) < num) return false;
                }
            }

            // 规则2：顶点约束（每个点最多两条边，且不能形成角上的死胡同）
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    int[] pEdges = getPointEdges(r, c);
                    int on = 0, off = 0;
                    for (int e : pEdges) {
                        if (e == 1) on++;
                        else if (e == -1) off++;
                    }

                    // 若有线数达到2，其余必须无钱
                    if (on == 2) {
                        for (int i = 0; i < pEdges.length; i++) {
                            if (pEdges[i] == 0) {
                                if (!setEdgeByPointDir(r, c, i, -1)) return false;
                                changed = true;
                            }
                        }
                    }
                    // 若 有线数+未确定数 < 2，无法达到回路要求（除单点外不可能）
                    // 若 有线数 > 2，矛盾
                    if (on > 2) return false;
                }
            }

            // 规则3：避免角上的一条线导致死胡同
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    int[] pEdges = getPointEdges(r, c);
                    int on = 0;
                    for (int e : pEdges) if (e == 1) on++;
                    if (on == 1) {
                        // 若某点只有一条线，且其相邻两条边都无钱，则另一条邻边也必须有线（避免死胡同）
                        // 简化处理：若某点只有1条有线和2条无钱边，则第4条必须有线
                        // 此规则已在顶点约束中部分覆盖
                    }
                }
            }
        }
        return true;
    }

    /**
     * 根据格子方向设置边状态
     * dir: 0=上, 1=下, 2=左, 3=右
     */
    private boolean setEdgeByCellDir(int r, int c, int dir, int state) {
        int old;
        if (dir == 0) { old = hEdges[r][c]; hEdges[r][c] = state; }
        else if (dir == 1) { old = hEdges[r + 1][c]; hEdges[r + 1][c] = state; }
        else if (dir == 2) { old = vEdges[r][c]; vEdges[r][c] = state; }
        else { old = vEdges[r][c + 1]; vEdges[r][c + 1] = state; }

        if (old != 0 && old != state) return false; // 与已有确定值矛盾
        return true;
    }

    /**
     * 获取某点连接的所有边 [上,下,左,右]，边界处缺失的边视为无钱(-1)
     */
    private int[] getPointEdges(int r, int c) {
        List<Integer> edges = new ArrayList<>();
        // 上
        if (r > 0) edges.add(hEdges[r - 1][c]);
        // 下
        if (r < rows - 1) edges.add(hEdges[r][c]);
        // 左
        if (c > 0) edges.add(vEdges[r][c - 1]);
        // 右
        if (c < cols - 1) edges.add(vEdges[r][c]);
        return edges.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 根据点方向设置边状态
     * dir顺序与getPointEdges一致
     */
    private boolean setEdgeByPointDir(int r, int c, int dir, int state) {
        List<int[]> coords = new ArrayList<>();
        if (r > 0) coords.add(new int[]{0, r - 1, c}); // hEdges[r-1][c]
        if (r < rows - 1) coords.add(new int[]{0, r, c}); // hEdges[r][c]
        if (c > 0) coords.add(new int[]{1, r, c - 1}); // vEdges[r][c-1]
        if (c < cols - 1) coords.add(new int[]{1, r, c}); // vEdges[r][c]

        if (dir >= coords.size()) return true;
        int[] co = coords.get(dir);
        int old;
        if (co[0] == 0) { old = hEdges[co[1]][co[2]]; hEdges[co[1]][co[2]] = state; }
        else { old = vEdges[co[1]][co[2]]; vEdges[co[1]][co[2]] = state; }

        if (old != 0 && old != state) return false;
        return true;
    }

3.3 并查集回路检测与回溯求解

“`java /*
* 检查当前已确定的边是否形成非法回路
* 使用并查集检测：若添加一条边后其两个端点已在同一集合，则形成回路
/
private boolean hasIllegalLoop() {
initUnionFind();
int edgeCount = 0;

    // 遍历所有确定的边，用并查集维护连通性
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols - 1; c++) {
            if (hEdges[r][c] == 1) {
                int p1 = pointId(r, c);
                int p2 = pointId(r, c + 1);
                if (!union(p1, p2)) {
                    // 形成回路，检查是否是最终解（所有边已确定且无未约束）
                    if (!isCompleteSolution()) return true;
                }
                edgeCount++;
            }
        }
    }
    for (int r = 0; r < rows - 1; r++) {
        for (int c = 0; c < cols; c++) {
            if (vEdges[r][c] == 1) {
                int p1 = pointId(r, c);
                int p2 = pointId(r + 1, c);
                if (!union(p1, p2)) {
                    if (!isCompleteSolution()) return true;
                }
                edgeCount++;
            }
        }
    }

    // 检查是否所有有线边属于同一连通分量（且至少有一条边）
    if (edgeCount > 0) {
        int root = -1;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                // 只检查有线边连接的端点
                boolean connected = false;
                if (c < cols - 1 && hEdges[r][c] == 1) connected = true;
                if (r < rows - 1 && vEdges[r][c] == 1) connected = true;
                if (c > 0 && hEdges[r][c - 1] == 1) connected = true;
                if (r > 0 && vEdges[r - 1][c] == 1) connected = true;

                if (connected) {
                    int pid = pointId(r, c);
                    int pr = find(pid);
                    if (root == -1) root = pr;
                    else if (root != pr) {
                        // 有线边形成多个不连通分量，不是最终解则暂时允许
                        // 但在最终解中必须是单一回路
                    }
                }
            }
        }
    }

    return false;
}

/**
 * 检查是否所有边都已确定且所有约束满足
 */
private boolean isCompleteSolution() {
    // 检查所有边是否都已确定
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols - 1; c++) {
            if (hEdges[r][c] == 0) return false;
        }
    }
    for (int r = 0; r < rows - 1; r++) {
        for (int c = 0; c < cols; c++) {
            if (vEdges[r][c] == 0) return false;
        }
    }

    // 检查数字约束
    for (int r = 0; r < rows - 1; r++) {
        for (int c = 0; c < cols - 1; c++) {
            if (numbers[r][c] < 0) continue;
            int[] counts = countCellEdges(r, c);
            if (counts[0] != numbers[r][c]) return false;
        }
    }

    // 检查顶点约束：每个点0或2条线
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int[] pEdges = getPointEdges(r, c);
            int on = 0;
            for (int e : pEdges) if (e == 1) on++;
            if (on != 0 && on != 2) return false;
        }
    }

    return true;
}

/**
 * 回溯求解主函数
 */
public boolean solve() {
    // 先进行约束传播
    if (!propagate()) return false;
    if (isCompleteSolution()) return true;

    // 选择第一个未确定的边进行分支
    int[] edge = findFirstUndeterminedEdge();
    if (edge == null) {
        // 所有边确定但约束传播未检测出解（理论上不应发生）
        return isCompleteSolution();
    }

    // 保存当前状态
    int[][] savedH = deepCopy(hEdges);
    int[][] savedV = deepCopy(vEdges);

    // 分支1：尝试设为有线
    if (edge[0] == 0) setHEdge(edge[1], edge[2], 1);
    else setVEdge(edge[1], edge[2], 1);

    if (!hasIllegalLoop()) {
        if (solve()) return true;
    }

    // 恢复状态
    hEdges = deepCopy(savedH);
    vEdges = deepCopy(savedV);

    // 分支2：尝试设为无钱
    if (edge[0] == 0) setHEdge(edge[1], edge[2], -1);
    else setVEdge(edge[1], edge[2], -1);

    if (!hasIllegalLoop()) {
        if (solve()) return true;
    }

    // 恢复状态
    hEdges = deepCopy(savedH);
    vEdges = deepCopy(savedV);

    return false;
}

private int[] findFirstUndeterminedEdge() {
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols - 1; c++) {
            if (hEdges[r][c] == 0) return new int[]{0, r, c};
        }
    }
    for (int r = 0; r < rows - 1; r++) {
        for (int c = 0; c < cols; c++) {
            if (vEdges[r][c] == 0) return new int[]{1, r, c};
        }
    }
    return null;
}

private int[][] deepCopy(int[][] arr) {
    int[][] copy = new int[arr.length][];
    for (int i = 0; i < arr.length; i++) copy[i] = arr[i].clone();
    return copy;
}

### 3.4 可视化与演示

```java    /**
     * ASCII可视化数回棋盘和解
     */
    public void printBoard() {
        System.out.println("\n=== 数回棋盘 ===");
        // 打印数字网格
        for (int r = 0; r < rows - 1; r++) {
            // 打印点行和水平边
            System.out.print("·");
            for (int c = 0; c < cols - 1; c++) {
                System.out.print(hEdges[r][c] == 1 ? "───" : hEdges[r][c] == -1 ? "   " : " . ");
                System.out.print("·");
            }
            System.out.println();

            // 打印垂直边和数字
            for (int c = 0; c < cols - 1; c++) {
                System.out.print(vEdges[r][c] == 1 ? "│" : vEdges[r][c] == -1 ? " " : ":");
                System.out.print(" ");
                if (numbers[r][c] >= 0) System.out.print(numbers[r][c]);
                else System.out.print(" ");
                System.out.print(" ");
            }
            System.out.print(vEdges[r][cols - 1] == 1 ? "│" : vEdges[r][cols - 1] == -1 ? " " : ":");
            System.out.println();
        }

        // 最后一行点
        System.out.print("·");
        for (int c = 0; c < cols - 1; c++) {
            System.out.print(hEdges[rows - 1][c] == 1 ? "───" : hEdges[rows - 1][c] == -1 ? "   " : " . ");
            System.out.print("·");
        }
        System.out.println();
    }

    /**
     * 打印纯回路图（隐藏数字）
     */
    public void printSolution() {
        System.out.println("\n=== 回路解 ===");
        for (int r = 0; r < rows - 1; r++) {
            System.out.print("○");
            for (int c = 0; c < cols - 1; c++) {
                System.out.print(hEdges[r][c] == 1 ? "───" : "   ");
                System.out.print("○");
            }
            System.out.println();

            for (int c = 0; c < cols; c++) {
                System.out.print(vEdges[r][c] == 1 ? "│" : " ");
                if (c < cols - 1) System.out.print("   ");
            }
            System.out.println();
        }
        System.out.print("○");
        for (int c = 0; c < cols - 1; c++) {
            System.out.print(hEdges[rows - 1][c] == 1 ? "───" : "   ");
            System.out.print("○");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.println("=== 数回求解器 ===\n");

        // 示例谜题1：5x5点阵（4x4数字格）
        int[][] puzzle1 = {
            { 2, -1, -1, 3},
            {-1,  3, -1, -1},
            {-1, -1,  2, -1},
            { 3, -1, -1,  2}
        };

        System.out.println("【谜题1】4x4");
        SlitherlinkSolver solver1 = new SlitherlinkSolver(puzzle1);
        solver1.printBoard();
        long t1 = System.currentTimeMillis();
        boolean solved1 = solver1.solve();
        long t2 = System.currentTimeMillis();
        System.out.println("求解结果: " + (solved1 ? "成功" : "失败") + "，耗时: " + (t2 - t1) + "ms");
        if (solved1) solver1.printSolution();

        // 示例谜题2：更复杂的6x6点阵
        int[][] puzzle2 = {
            { 3, -1,  2, -1, 1},
            {-1,  2, -1,  3,-1},
            { 1, -1,  3, -1, 2},
            {-1,  3, -1,  2,-1},
            { 2, -1,  1, -1, 3}
        };

        System.out.println("\n【谜题2】5x5");
        SlitherlinkSolver solver2 = new SlitherlinkSolver(puzzle2);
        solver2.printBoard();
        long t3 = System.currentTimeMillis();
        boolean solved2 = solver2.solve();
        long t4 = System.currentTimeMillis();
        System.out.println("求解结果: " + (solved2 ? "成功" : "失败") + "，耗时: " + (t4 - t3) + "ms");
        if (solved2) solver2.printSolution();

        // 示例谜题3：经典"全3"难题
        int[][] puzzle3 = {
            {3, 3, 3},
            {3, 3, 3},
            {3, 3, 3}
        };

        System.out.println("\n【谜题3】全3经典难题 4x4");
        SlitherlinkSolver solver3 = new SlitherlinkSolver(puzzle3);
        solver3.printBoard();
        long t5 = System.currentTimeMillis();
        boolean solved3 = solver3.solve();
        long t6 = System.currentTimeMillis();
        System.out.println("求解结果: " + (solved3 ? "成功" : "失败") + "，耗时: " + (t6 - t5) + "ms");
        if (solved3) solver3.printSolution();
    }
}

四、复杂度分析

对于10×10以下的常见谜题，约束传播通常可确定50%-90%的边，剩余少量未知边通过回溯在毫秒级求解。

五、总结

本文用Java实现了数回（Slitherlink）逻辑解谜游戏的完整求解器，核心亮点包括：

1. 约束传播引擎：通过数字约束和顶点约束双向推导，快速确定大量边状态，避免无效搜索
2. 并查集回路检测：高效检测已确定边是否形成非法小回路，在搜索早期剪除大量不可能分支
3. 深度优先回溯：对剩余未确定边进行二元分支（有线/无钱），结合约束传播实现增量验证
4. 可视化输出：ASCII字符绘制原始谜题和回路解，直观展示求解结果

读者可进一步扩展以下方向：
– 加入高级约束规则（如边长限制、区域连通性）进一步提升传播效率
– 用启发式排序选择分支边（优先选择受约束最多的边）减少回溯深度
– 接入 puzzle 数据库批量测试，统计各类谜题的平均求解时间
– 将求解器改造为逐步提示系统，在玩家卡关时给出下一步推理建议