每日算法 — 使用java实现Slitherlink：约束满足与边界传播求解

引言

Slitherlink（数回/环 surrounding）是一款由Nikoli推出的经典逻辑拼图：玩家在点阵网格的边上画线，形成一条唯一的闭合环路，每个带数字的格子表示其四周边上线的数量（0-3）。与数独、数织类似，Slitherlink的求解属于约束满足问题（CSP），但其约束作用于边而非单元格，且全局需满足单环连通性这一拓扑约束。

问题建模

一个 $R \times C$ 的Slitherlink谜题包含：
– 点：$(R+1) \times (C+1)$ 个格点
– 水平边：$R \times (C+1)$ 条
– 垂直边：$(R+1) \times C$ 条
– 数字约束：部分格子标注 0-3，要求该格子四周的已画边数恰好等于该数字
– 全局约束：所有画线边构成恰好一条简单闭合环路

将每条边的状态编码为：-1=未知, 0=不画, 1=画线。

核心算法一：局部约束传播（Local Edge Propagation）

数字约束是最直接的推理来源。例如数字 3 表示四边中恰好3条被画，等价于恰好1条不画；数字 0 表示四边均不画。结合相邻格子的约束可推导出更多必然状态。

/**
 * Slitherlink局部约束传播引擎
 * 基于每个格子的数字约束和基本几何关系推导边的必然状态
 */
public class SlitherlinkPropagator {

    // 边的状态：-1=未知, 0=不画, 1=画线
    private int[][] hEdges; // 水平边 [R][C+1]
    private int[][] vEdges; // 垂直边 [R+1][C]
    private int[][] clues;  // 数字提示 [R][C]，-1表示无提示
    private final int rows, cols;

    public SlitherlinkPropagator(int[][] clues) {
        this.clues = clues;
        this.rows = clues.length;
        this.cols = clues[0].length;
        this.hEdges = new int[rows][cols + 1];
        this.vEdges = new int[rows + 1][cols];
        for (int[] row : hEdges) java.util.Arrays.fill(row, -1);
        for (int[] row : vEdges) java.util.Arrays.fill(row, -1);
    }

    /**
     * 获取某格子四周四条边的状态
     * 顺序：上(水平)、下(水平)、左(垂直)、右(垂直)
     */
    private int[] getCellEdges(int r, int c) {
        return new int[]{
            hEdges[r][c],       // 上边
            hEdges[r + 1][c],   // 下边
            vEdges[r][c],       // 左边
            vEdges[r + c < cols ? 1 : 0][c] // 右边
        };
    }

    // 修正getCellEdges
    private int[] getCellEdgesFixed(int r, int c) {
        return new int[]{
            hEdges[r][c],       // 上边 (r,c)到(r,c+1)
            hEdges[r + 1][c],   // 下边 (r+1,c)到(r+1,c+1)
            vEdges[r][c],       // 左边 (r,c)到(r+1,c)
            vEdges[r][c + 1]    // 右边 (r,c+1)到(r+1,c+1)
        };
    }

    /**
     * 执行一轮完整的局部约束传播
     * @return true表示有状态被更新，false表示已达不动点
     */
    public boolean propagate() {
        boolean changed = false;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (clues[r][c] >= 0) {
                    if (propagateCell(r, c, clues[r][c])) changed = true;
                }
            }
        }
        // 传播角点和边的点度约束（每个点度数必须为0或2）
        if (propagateVertexDegree()) changed = true;
        return changed;
    }

    /**
     * 对单个数字格子进行约束传播
     * @param clue 数字要求（0-3）
     * @return 是否有更新
     */
    private boolean propagateCell(int r, int c, int clue) {
        boolean changed = false;
        int[] edges = getCellEdgesFixed(r, c);
        int[] edgeRefs = {
            encodeEdge(0, r, c), encodeEdge(0, r + 1, c),
            encodeEdge(1, r, c), encodeEdge(1, r, c + 1)
        };

        int unknownCount = 0, drawCount = 0, emptyCount = 0;
        for (int e : edges) {
            if (e == -1) unknownCount++;
            else if (e == 1) drawCount++;
            else emptyCount++;
        }

        // 已画边数 + 未知边数 < clue => 矛盾（不可能满足）
        // 已画边数 > clue => 矛盾
        if (drawCount > clue || drawCount + unknownCount < clue) {
            throw new IllegalStateException("矛盾 detected at cell (" + r + "," + c + ")");
        }

        // 若已画边数 == clue，则所有未知边必须不画
        if (drawCount == clue) {
            for (int i = 0; i < 4; i++) {
                if (edges[i] == -1) {
                    setEdge(edgeRefs[i], 0);
                    changed = true;
                }
            }
        }
        // 若已画边数 + 未知边数 == clue，则所有未知边必须画
        else if (drawCount + unknownCount == clue) {
            for (int i = 0; i < 4; i++) {
                if (edges[i] == -1) {
                    setEdge(edgeRefs[i], 1);
                    changed = true;
                }
            }
        }
        return changed;
    }

    /**
     * 点度约束传播：每个格点的度数必须为0或2（环路的局部特性）
     * 每个内部点连接4条边，角点连接2条边，边点连接3条边
     */
    private boolean propagateVertexDegree() {
        boolean changed = false;
        for (int r = 0; r <= rows; r++) {
            for (int c = 0; c <= cols; c++) {
                int[] incident = getIncidentEdges(r, c);
                int unknown = 0, drawn = 0;
                for (int e : incident) {
                    int val = decodeEdgeValue(e);
                    if (val == -1) unknown++;
                    else if (val == 1) drawn++;
                }

                // 每个点在环路中度数必须为0或2
                // 若已画1条且剩余全为未知，则必须再画1条（度数至少2）
                // 若已画2条，则其余必须不画
                // 若已画0条且只剩1条未知，则该条必须不画（否则度数为1）

                if (drawn == 2) {
                    for (int e : incident) {
                        if (decodeEdgeValue(e) == -1) {
                            setEdge(e, 0);
                            changed = true;
                        }
                    }
                } else if (drawn == 1 && unknown == 1) {
                    for (int e : incident) {
                        if (decodeEdgeValue(e) == -1) {
                            setEdge(e, 1);
                            changed = true;
                        }
                    }
                } else if (drawn == 0 && unknown == 1) {
                    for (int e : incident) {
                        if (decodeEdgeValue(e) == -1) {
                            setEdge(e, 0);
                            changed = true;
                        }
                    }
                }
            }
        }
        return changed;
    }

    // 边的编码：type*10000 + r*100 + c，type:0=水平,1=垂直
    private int encodeEdge(int type, int r, int c) { return type * 10000 + r * 100 + c; }

    private void setEdge(int encoded, int value) {
        int type = encoded / 10000;
        int r = (encoded % 10000) / 100;
        int c = encoded % 100;
        if (type == 0) hEdges[r][c] = value;
        else vEdges[r][c] = value;
    }

    private int decodeEdgeValue(int encoded) {
        int type = encoded / 10000;
        int r = (encoded % 10000) / 100;
        int c = encoded % 100;
        return type == 0 ? hEdges[r][c] : vEdges[r][c];
    }

    /**
     * 获取某点关联的所有边编码
     */
    private int[] getIncidentEdges(int r, int c) {
        java.util.List<Integer> edges = new java.util.ArrayList<>();
        if (r > 0) edges.add(encodeEdge(0, r - 1, c)); // 上方水平边
        if (r < rows) edges.add(encodeEdge(0, r, c));   // 下方水平边
        if (c > 0) edges.add(encodeEdge(1, r, c - 1)); // 左方垂直边
        if (c < cols) edges.add(encodeEdge(1, r, c));   // 右方垂直边
        int[] result = new int[edges.size()];
        for (int i = 0; i < edges.size(); i++) result[i] = edges.get(i);
        return result;
    }

    public int[][] getHEdges() { return hEdges; }
    public int[][] getVEdges() { return vEdges; }
}

核心算法二：连通性检测与避免子环路

局部约束传播无法完全保证全局单环约束。回溯搜索中，每次画线后必须通过并查集检测是否形成非法子环路，同时确保不制造度数超过2的点。

/**
 * 基于并查集的环路检测器
 * 追踪已画线边的连通分量，防止过早闭合子环路
 */
public class LoopDetector {
    // 每个格点编码为 id = r * (cols+1) + c
    private int[] parent;
    private int rows, cols;

    public LoopDetector(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.parent = new int[(rows + 1) * (cols + 1)];
        for (int i = 0; i < parent.length; i++) parent[i] = i;
    }

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

    private void union(int a, int b) {
        parent[find(a)] = find(b);
    }

    /**
     * 检查在两点之间添加边是否会形成非法子环路
     * @param r1, c1 端点1
     * @param r2, c2 端点2
     * @param totalDrawnEdges 当前已画线边总数
     * @return true表示允许添加（不形成非法环），false表示会形成子环
     */
    public boolean canAddEdge(int r1, int c1, int r2, int c2, int totalDrawnEdges) {
        int id1 = r1 * (cols + 1) + c1;
        int id2 = r2 * (cols + 1) + c2;
        int root1 = find(id1);
        int root2 = find(id2);

        if (root1 == root2) {
            // 若两点已在同一连通分量，添加边会形成环
            // 仅当这是最后一条边（形成完整大环）时才允许
            int totalPossibleEdges = rows * (cols + 1) + (rows + 1) * cols;
            return totalDrawnEdges + 1 == totalPossibleEdges; // 简化判断，实际需要更精确
        }
        return true;
    }

    public void addEdge(int r1, int c1, int r2, int c2) {
        union(r1 * (cols + 1) + c1, r2 * (cols + 1) + c2);
    }
}

核心算法三：完整求解器（传播 + 回溯）

/**
 * Slitherlink完整求解器
 */
public class SlitherlinkSolver {
    private int[][] clues;
    private int rows, cols;
    private SlitherlinkPropagator propagator;

    public SlitherlinkSolver(int[][] clues) {
        this.clues = clues;
        this.rows = clues.length;
        this.cols = clues[0].length;
    }

    public boolean solve() {
        propagator = new SlitherlinkPropagator(clues);
        try {
            while (propagator.propagate()) {} // 传播至不动点
        } catch (IllegalStateException e) {
            return false; // 矛盾
        }

        if (isComplete()) return isValidSolution();

        // 选择第一条未知边进行分支
        int[] firstUnknown = findFirstUnknown();
        if (firstUnknown == null) return isValidSolution();

        // 保存状态
        int[][] savedH = deepCopy(propagator.getHEdges());
        int[][] savedV = deepCopy(propagator.getVEdges());

        // 分支1：画线
        propagator = new SlitherlinkPropagator(clues);
        restoreState(savedH, savedV);
        setEdge(firstUnknown, 1);
        if (solve()) return true;

        // 分支2：不画
        propagator = new SlitherlinkPropagator(clues);
        restoreState(savedH, savedV);
        setEdge(firstUnknown, 0);
        if (solve()) return true;

        return false;
    }

    private boolean isComplete() {
        for (int[][] edges : new int[][][]{propagator.getHEdges(), propagator.getVEdges()}) {
            for (int[] row : edges) {
                for (int v : row) if (v == -1) return false;
            }
        }
        return true;
    }

    private boolean isValidSolution() {
        // 验证所有数字约束
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (clues[r][c] >= 0) {
                    // 统计四周画线边数
                    int count = 0;
                    // 简化：此处应调用完整验证逻辑
                }
            }
        }
        // 验证单环连通性
        return true;
    }

    private int[] findFirstUnknown() {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c <= cols; c++) {
                if (propagator.getHEdges()[r][c] == -1) return new int[]{0, r, c};
            }
        }
        for (int r = 0; r <= rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (propagator.getVEdges()[r][c] == -1) return new int[]{1, r, c};
            }
        }
        return null;
    }

    private void setEdge(int[] info, int val) {
        // 通过反射或重新设计Propagator来支持外部设置
    }

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

    private void restoreState(int[][] h, int[][] v) {
        // 状态恢复逻辑
    }

    /**
     * 打印求解结果
     */
    public void printSolution() {
        int[][] h = propagator.getHEdges();
        int[][] v = propagator.getVEdges();
        for (int r = 0; r <= rows; r++) {
            // 打印水平边和点
            for (int c = 0; c <= cols; c++) {
                System.out.print("+");
                if (c < cols && r < rows && h[r][c] == 1) System.out.print("---");
                else if (c < cols) System.out.print("   ");
            }
            System.out.println();
            if (r < rows) {
                for (int c = 0; c <= cols; c++) {
                    if (c < cols && v[r][c] == 1) System.out.print("|   ");
                    else if (c < cols) System.out.print("    ");
                    if (c < cols && clues[r][c] >= 0) {
                        // 回退打印数字
                        System.out.print("\b\b" + clues[r][c] + " ");
                    }
                }
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        // 3x3 简单谜题示例
        int[][] clues = {
            {2, 1, 2},
            {1, -1, 1},
            {2, 1, 2}
        };
        SlitherlinkSolver solver = new SlitherlinkSolver(clues);
        if (solver.solve()) {
            System.out.println("求解成功！");
            solver.printSolution();
        } else {
            System.out.println("无解");
        }
    }
}

标准局部推理模式速查

复杂度分析

扩展方向

1. 高级局部模式：预编译更多相邻数字组合的高阶推理规则
2. 区域分析法：通过平面图的欧拉公式和区域计数辅助剪枝
3. 交互式提示系统：为玩家提供下一步可推导的边位置
4. 谜题生成：从随机环路反向推导数字提示，确保唯一解

总结

Slitherlink求解器展示了边级约束满足问题的独特魅力。与单元格级CSP（如数独）不同，Slitherlink的约束跨越边和点两个层级，且全局拓扑约束要求环路唯一性。通过局部约束传播处理必然状态、用并查集防止子环路、最后以回溯搜索处理剩余不确定性，这一三层架构可高效求解绝大多数标准难度谜题。