每日算法 — 使用java实现数桥：DFS连通性检测与约束传播

引言

数桥（Hashiwokakero）是一款源自日本的经典逻辑谜题，玩家需要在标有数字的岛屿之间搭建桥梁，使所有岛屿连通成一片，同时满足每个岛屿标注的数字约束。数桥问题本质上是约束满足问题（CSP）与图论连通性的结合，非常适合用回溯搜索与深度优先搜索（DFS）求解。

本文将用Java完整实现数桥求解器，涵盖问题建模、约束传播、回溯搜索与连通性验证等核心算法。

问题规则与算法思路

数桥规则

1. 棋盘上分布着若干标有数字（1-8）的岛屿。
2. 岛屿之间可以搭水平或垂直的桥，桥不能转弯。
3. 两岛之间最多搭建2座桥。
4. 桥与桥之间不能交叉。
5. 每个岛屿最终的桥数必须等于其标注的数字。
6. 所有岛屿必须通过桥相互连通。

核心算法思路

求解数桥采用回溯搜索 + 约束传播 + DFS连通性检测的组合策略：

• 图论建模：将每个岛屿视为图中的节点，候选桥视为带权边（权重0-2）。
• 约束传播：对每个岛屿，根据剩余度数和候选邻居，确定某些边是否必须存在或必须排除。
• 回溯搜索：按优先级选择约束最强的岛屿，枚举其桥的分布情况，递归求解。
• 连通性剪枝：每次赋值后，用DFS检查当前图是否仍可能连通，提前剪掉无效分支。
• 连通性验证：最终解必须满足所有岛屿通过桥相互可达。

完整Java实现

import java.util.*;

/**
 * 数桥（Hashiwokakero）求解器
 * 核心算法：回溯搜索 + 约束传播 + DFS连通性检测
 */
public class HashiSolver {

    // 表示一个岛屿节点
    static class Island {
        int id;          // 唯一编号
        int r, c;        // 行、列坐标
        int required;    // 要求的桥数量
        int current;     // 当前已连接的桥数量

        Island(int id, int r, int c, int required) {
            this.id = id;
            this.r = r;
            this.c = c;
            this.required = required;
            this.current = 0;
        }
    }

    // 表示两岛之间的候选桥
    static class Bridge {
        Island a, b;     // 连接的两个岛屿
        int maxAllowed;  // 最大允许桥数（通常是2）
        int current;     // 当前桥数（0, 1, 2）
        boolean isHorizontal; // 是否水平桥

        Bridge(Island a, Island b) {
            this.a = a;
            this.b = b;
            this.maxAllowed = 2;
            this.current = 0;
            this.isHorizontal = a.r == b.r;
        }
    }

    private List<Island> islands;
    private List<Bridge> bridges;
    private Map<Island, List<Bridge>> islandToBridges;
    private int rows, cols;
    private boolean solved;
    private int[][] solutionGrid; // 用于可视化输出

    public HashiSolver(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.islands = new ArrayList<>();
        this.bridges = new ArrayList<>();
        this.islandToBridges = new HashMap<>();
        this.solved = false;
    }

    /**
     * 添加岛屿
     */
    public void addIsland(int r, int c, int required) {
        Island island = new Island(islands.size(), r, c, required);
        islands.add(island);
        islandToBridges.put(island, new ArrayList<>());
    }

    /**
     * 构建候选桥：两岛如果在同一行或同一列且中间无其他岛，则可搭桥
     */
    public void buildCandidateBridges() {
        // 按行分组，找水平候选桥
        Map<Integer, List<Island>> rowMap = new HashMap<>();
        for (Island is : islands) {
            rowMap.computeIfAbsent(is.r, k -> new ArrayList<>()).add(is);
        }
        for (List<Island> list : rowMap.values()) {
            list.sort(Comparator.comparingInt(i -> i.c));
            for (int i = 0; i < list.size() - 1; i++) {
                Island a = list.get(i);
                Island b = list.get(i + 1);
                // 检查中间是否有其他岛屿阻挡
                if (!hasIslandBetween(a.r, a.c, b.c, true)) {
                    Bridge br = new Bridge(a, b);
                    bridges.add(br);
                    islandToBridges.get(a).add(br);
                    islandToBridges.get(b).add(br);
                }
            }
        }

        // 按列分组，找垂直候选桥
        Map<Integer, List<Island>> colMap = new HashMap<>();
        for (Island is : islands) {
            colMap.computeIfAbsent(is.c, k -> new ArrayList<>()).add(is);
        }
        for (List<Island> list : colMap.values()) {
            list.sort(Comparator.comparingInt(i -> i.r));
            for (int i = 0; i < list.size() - 1; i++) {
                Island a = list.get(i);
                Island b = list.get(i + 1);
                if (!hasIslandBetween(a.c, a.r, b.r, false)) {
                    Bridge br = new Bridge(a, b);
                    bridges.add(br);
                    islandToBridges.get(a).add(br);
                    islandToBridges.get(b).add(br);
                }
            }
        }
    }

    /**
     * 检查两个岛屿之间是否有其他岛屿阻挡
     */
    private boolean hasIslandBetween(int fixed, int start, int end, boolean isRow) {
        int min = Math.min(start, end);
        int max = Math.max(start, end);
        for (Island is : islands) {
            if (isRow) {
                if (is.r == fixed && is.c > min && is.c < max) return true;
            } else {
                if (is.c == fixed && is.r > min && is.r < max) return true;
            }
        }
        return false;
    }

    /**
     * 约束传播：根据每个岛屿的剩余度数，确定必建或必不建的桥
     * 返回false表示出现矛盾
     */
    private boolean propagateConstraints() {
        boolean changed = true;
        while (changed) {
            changed = false;
            for (Island is : islands) {
                int remaining = is.required - is.current;
                List<Bridge> candidates = islandToBridges.get(is);
                // 只考虑还能增加桥的候选
                List<Bridge> available = new ArrayList<>();
                int maxPossible = 0;
                for (Bridge br : candidates) {
                    if (br.current < br.maxAllowed) {
                        available.add(br);
                        maxPossible += (br.maxAllowed - br.current);
                    }
                }

                // 如果剩余度数大于最大可能增量，矛盾
                if (remaining > maxPossible) return false;
                // 如果剩余度数为0，所有可用候选必须关闭
                if (remaining == 0) {
                    for (Bridge br : available) {
                        if (br.current < br.maxAllowed) {
                            br.maxAllowed = br.current; // 锁定为当前值
                            changed = true;
                        }
                    }
                }
                // 如果剩余度数等于可用候选的最大增量之和，则每个可用候选必须满建
                if (remaining == maxPossible && remaining > 0) {
                    for (Bridge br : available) {
                        if (br.current < br.maxAllowed) {
                            int add = br.maxAllowed - br.current;
                            br.current = br.maxAllowed;
                            br.a.current += add;
                            br.b.current += add;
                            changed = true;
                        }
                    }
                }
            }
        }
        return true;
    }

    /**
     * 检查当前桥配置下，图是否可能最终连通
     * 使用DFS检测：忽略未赋值的桥，看当前已建桥构成的图是否可能扩展为连通图
     */
    private boolean isPotentiallyConnected() {
        if (islands.isEmpty()) return true;
        Set<Island> visited = new HashSet<>();
        dfsConnectivity(islands.get(0), visited);
        // 对于未访问的岛屿，检查是否还有候选桥可以连接到已访问集合
        for (Island is : islands) {
            if (!visited.contains(is)) {
                boolean canReach = false;
                for (Bridge br : islandToBridges.get(is)) {
                    if (br.current > 0 || br.maxAllowed > br.current) {
                        Island other = (br.a == is) ? br.b : br.a;
                        if (visited.contains(other)) {
                            canReach = true;
                            break;
                        }
                    }
                }
                if (!canReach) return false;
            }
        }
        return true;
    }

    private void dfsConnectivity(Island start, Set<Island> visited) {
        visited.add(start);
        for (Bridge br : islandToBridges.get(start)) {
            if (br.current > 0) {
                Island other = (br.a == start) ? br.b : br.a;
                if (!visited.contains(other)) {
                    dfsConnectivity(other, visited);
                }
            }
        }
    }

    /**
     * 最终验证：所有岛屿是否通过桥完全连通
     */
    private boolean verifyFinalConnectivity() {
        if (islands.isEmpty()) return true;
        Set<Island> visited = new HashSet<>();
        dfsConnectivity(islands.get(0), visited);
        return visited.size() == islands.size();
    }

    /**
     * 回溯搜索主入口
     */
    public boolean solve() {
        if (!propagateConstraints()) return false;
        if (!isPotentiallyConnected()) return false;
        return backtrack();
    }

    /**
     * 回溯搜索：选择约束最强的岛屿进行分支
     */
    private boolean backtrack() {
        // 检查是否所有岛屿都满足
        boolean allSatisfied = true;
        for (Island is : islands) {
            if (is.current != is.required) {
                allSatisfied = false;
                break;
            }
        }
        if (allSatisfied) {
            return verifyFinalConnectivity();
        }

        // 选择剩余约束最强的岛屿（可用分支最少）
        Island bestIsland = null;
        int minBranches = Integer.MAX_VALUE;
        for (Island is : islands) {
            int remaining = is.required - is.current;
            if (remaining <= 0) continue;
            List<Bridge> candidates = islandToBridges.get(is);
            int branches = 0;
            for (Bridge br : candidates) {
                if (br.current < br.maxAllowed) branches++;
            }
            if (branches < minBranches && branches > 0) {
                minBranches = branches;
                bestIsland = is;
            }
        }

        if (bestIsland == null) return false;

        // 收集该岛屿的所有可用候选桥
        List<Bridge> available = new ArrayList<>();
        for (Bridge br : islandToBridges.get(bestIsland)) {
            if (br.current < br.maxAllowed) available.add(br);
        }

        int remaining = bestIsland.required - bestIsland.current;
        // 枚举所有可能的桥数分配（简化：按顺序尝试每条桥增加1或2）
        return tryBridges(bestIsland, available, 0, remaining);
    }

    /**
     * 递归尝试为岛屿分配桥数
     */
    private boolean tryBridges(Island island, List<Bridge> available, int idx, int remaining) {
        if (remaining == 0) {
            // 保存当前状态
            int[] oldCurrents = new int[available.size()];
            int[] oldMaxes = new int[available.size()];
            for (int i = 0; i < available.size(); i++) {
                oldCurrents[i] = available.get(i).current;
                oldMaxes[i] = available.get(i).maxAllowed;
            }
            int[] oldIslandCurrents = new int[islands.size()];
            for (int i = 0; i < islands.size(); i++) oldIslandCurrents[i] = islands.get(i).current;

            // 关闭未使用的可用桥
            for (Bridge br : available) {
                if (br.current == 0) br.maxAllowed = 0;
            }

            if (propagateConstraints() && isPotentiallyConnected() && backtrack()) {
                return true;
            }

            // 恢复状态
            for (int i = 0; i < available.size(); i++) {
                available.get(i).current = oldCurrents[i];
                available.get(i).maxAllowed = oldMaxes[i];
            }
            for (int i = 0; i < islands.size(); i++) islands.get(i).current = oldIslandCurrents[i];
            return false;
        }
        if (idx >= available.size()) return false;

        Bridge br = available.get(idx);
        int maxAdd = Math.min(br.maxAllowed - br.current, remaining);

        // 尝试不增加这座桥
        int oldMax = br.maxAllowed;
        br.maxAllowed = br.current; // 暂时关闭
        if (tryBridges(island, available, idx + 1, remaining)) return true;
        br.maxAllowed = oldMax;

        // 尝试增加1座或2座桥
        for (int add = 1; add <= maxAdd; add++) {
            br.current += add;
            br.a.current += add;
            br.b.current += add;
            if (tryBridges(island, available, idx + 1, remaining - add)) return true;
            br.current -= add;
            br.a.current -= add;
            br.b.current -= add;
        }

        return false;
    }

    /**
     * 打印求解结果
     */
    public void printSolution() {
        System.out.println("=== 数桥求解结果 ===");
        for (Bridge br : bridges) {
            if (br.current > 0) {
                System.out.printf("岛屿(%d,%d) <-> 岛屿(%d,%d): %d座桥%n",
                    br.a.r, br.a.c, br.b.r, br.b.c, br.current);
            }
        }
    }

    public static void main(String[] args) {
        // 示例谜题：一个简单的数桥布局
        // 棋盘大小 5x5，岛屿位置及数字如下：
        HashiSolver solver = new HashiSolver(5, 5);
        solver.addIsland(0, 0, 2);
        solver.addIsland(0, 4, 2);
        solver.addIsland(2, 0, 3);
        solver.addIsland(2, 2, 4);
        solver.addIsland(2, 4, 3);
        solver.addIsland(4, 0, 2);
        solver.addIsland(4, 4, 2);

        solver.buildCandidateBridges();
        long start = System.currentTimeMillis();
        boolean solved = solver.solve();
        long end = System.currentTimeMillis();

        if (solved) {
            System.out.println("求解成功！耗时: " + (end - start) + "ms");
            solver.printSolution();
        } else {
            System.out.println("无解");
        }
    }
}

算法复杂度分析

总结

数桥求解器展示了约束满足问题的典型解法：通过图论建模将逻辑规则转化为数学约束，利用约束传播减少搜索空间，结合DFS连通性检测进行高效剪枝，最终通过回溯搜索找到满足所有条件的全局最优解。这套框架同样适用于扫雷、数独、KenKen等逻辑谜题的自动求解。