每日算法 — 使用java实现帐篷谜题：约束传播与二分图完美匹配求解

帐篷谜题（Tents）是《纽约时报》Logic Puzzles 里的常客，规则干净到一句话就能说完：网格里种了若干树，你要给每棵树配一顶帐篷，让帐篷与树一一配对且互不接触。听起来像连连看，实际是一个纯粹的约束满足问题（CSP），求解它的两种正统方法是约束传播与二分图完美匹配。

这篇文章用 Java 实现两种解法，并解释为什么对帐篷谜题而言，后者比暴力回溯快上千倍。

一、规则形式化

棋盘为 n × m 网格，每格三态：树（TREE）、草地（GRASS）、未知。约束如下：

1. 帐篷只能放在草地上（不能放树、不能放空）。
2. 每棵树恰好对应一顶帐篷，且该帐篷必须与树四邻（上下左右）相邻。
3. 任意两顶帐篷不能相邻，包括对角相邻（即 8 邻域内互斥）。
4. 行提示数：第 i 行的帐篷数量 = rowHint[i]；列提示数同理。

第 2 条是关键：它让”帐篷”与”树”之间形成匹配关系——每棵树恰好匹配一顶帐篷。这正是把问题转化为匹配问题的入口。

注意第 3 条的”八邻域互斥”是帐篷谜题区别于普通匹配的额外约束，它使得纯匹配解法需要额外处理，但也正是它让题目唯一可解。

二、候选域：从格到约束图

第一步是把每个格子能放什么算出来。

public enum Cell { UNKNOWN, TREE, GRASS, TENT }

public final class Puzzle {
    public final int rows, cols;
    public final Cell[][] grid;
    public final int[] rowHint;   // 每行帐篷数
    public final int[] colHint;   // 每列帐篷数

    public Puzzle(int rows, int cols, Cell[][] grid, int[] rowHint, int[] colHint) {
        this.rows = rows; this.cols = cols; this.grid = grid;
        this.rowHint = rowHint; this.colHint = colHint;
    }

    public boolean inBounds(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    /** 该格是否允许放帐篷（仅草地可放） */
    public boolean tentAllowed(int r, int c) {
        return inBounds(r, c) && grid[r][c] == Cell.GRASS;
    }
}

候选域的核心是”每棵树的可选帐篷位置”与”每个格可服务的树”。后者用于约束传播中的反查：

public final class Domains {
    private static final int[][] DIRS = { {-1,0}, {1,0}, {0,-1}, {0,1} };

    /** 树的可选帐篷格子列表：树编号 -> 候选格索引 */
    public static java.util.List<java.util.List<Integer>> tentOptionsForTrees(Puzzle p) {
        java.util.List<java.util.List<Integer>> out = new java.util.ArrayList<>();
        for (int r = 0; r < p.rows; r++) {
            for (int c = 0; c < p.cols; c++) {
                if (p.grid[r][c] != Cell.TREE) continue;
                java.util.List<Integer> opts = new java.util.ArrayList<>(4);
                for (int[] d : DIRS) {
                    int nr = r + d[0], nc = c + d[1];
                    if (p.tentAllowed(nr, nc)) opts.add(nr * p.cols + nc);
                }
                out.add(opts);
            }
        }
        return out;
    }

    /** 格的反向候选：该格能服务哪些树（树编号列表） */
    public static java.util.List<java.util.List<Integer>> treesForCell(Puzzle p) {
        int total = p.rows * p.cols;
        java.util.List<java.util.List<Integer>> out = new java.util.ArrayList<>(total);
        for (int i = 0; i < total; i++) out.add(new java.util.ArrayList<>());
        for (int r = 0; r < p.rows; r++) {
            for (int c = 0; c < p.cols; c++) {
                if (p.grid[r][c] != Cell.TREE) continue;
                int treeId = treeIndex(p, r, c);
                for (int[] d : DIRS) {
                    int nr = r + d[0], nc = c + d[1];
                    if (p.tentAllowed(nr, nc)) out.get(nr * p.cols + nc).add(treeId);
                }
            }
        }
        return out;
    }

    private static int treeIndex(Puzzle p, int r, int c) {
        int id = 0;
        for (int i = 0; i < p.rows; i++) {
            for (int j = 0; j < p.cols; j++) {
                if (p.grid[i][j] == Cell.TREE) {
                    if (i == r && j == c) return id;
                    id++;
                }
            }
        }
        return -1;
    }
}

treesForCell 里那个 O(rows·cols) 的 treeIndex 调用会把整体复杂度拉成 O((nm)²)，务必改成预建 int[][] treeIdAt 映射表。这类”看似无害的辅助函数”是逻辑谜题求解器最常见的性能杀手。

三、解法一：约束传播

帐篷谜题的提示数提供了极强的推理机会。典型的传播规则有四条：

规则 A（行/列饱和）：若某行的帐篷数已达到提示值，该行所有剩余空格必须标为草地；若该行剩余空格数恰好等于还缺的帐篷数，则全部标为帐篷。

规则 B（单候选树）：若某棵树只剩一个候选格，该格必为帐篷，并划掉同行同列其他候选。

规则 C（单服务格）：若某格原本能服务多棵树，但其他候选都被排除，只剩一棵树，则该格必为该树服务。

规则 D（八邻域禁放）：一旦确定某格是帐篷，它周围 8 格全部标为草地。

public final class Propagator {
    private static final int[][] DIRS8 = {
        {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
    };

    /** 返回是否发生冲突；通过修改 domains 原地传播 */
    public static boolean propagate(Puzzle p,
                                    java.util.List<java.util.List<Integer>> treeOpts,
                                    java.util.List<java.util.List<Integer>> cellTrees,
                                    boolean[] tentFixed, boolean[] grassFixed,
                                    int[] rowRemain, int[] colRemain) {

        boolean changed = true;
        while (changed) {
            changed = false;

            // 规则 D + 帐篷定案：标记八邻域禁放
            for (int r = 0; r < p.rows; r++) {
                for (int c = 0; c < p.cols; c++) {
                    if (!tentFixed[r * p.cols + c]) continue;
                    for (int[] d : DIRS8) {
                        int nr = r + d[0], nc = c + d[1];
                        if (!p.inBounds(nr, nc)) continue;
                        int idx = nr * p.cols + nc;
                        if (p.tentAllowed(nr, nc) && !grassFixed[idx]) {
                            grassFixed[idx] = true;
                            changed = true;
                            if (!eliminate(idx, treeOpts, cellTrees)) return false;
                        }
                    }
                }
            }

            // 规则 B：单候选树必须落在此格
            for (int t = 0; t < treeOpts.size(); t++) {
                java.util.List<Integer> opts = treeOpts.get(t);
                if (opts.size() == 1) {
                    int cell = opts.get(0);
                    if (!tentFixed[cell]) {
                        tentFixed[cell] = true;
                        changed = true;
                        int rr = cell / p.cols, cc = cell % p.cols;
                        rowRemain[rr]--; colRemain[cc]--;
                        if (rowRemain[rr] < 0 || colRemain[cc] < 0) return false;
                    }
                } else if (opts.isEmpty()) {
                    return false;   // 树无帐篷可配
                }
            }

            // 规则 A：行列饱和
            for (int r = 0; r < p.rows; r++) {
                if (rowRemain[r] == 0) {
                    for (int c = 0; c < p.cols; c++) {
                        int idx = r * p.cols + c;
                        if (p.tentAllowed(r, c) && !grassFixed[idx] && !tentFixed[idx]) {
                            grassFixed[idx] = true;
                            changed = true;
                            if (!eliminate(idx, treeOpts, cellTrees)) return false;
                        }
                    }
                }
            }
            for (int c = 0; c < p.cols; c++) {
                if (colRemain[c] == 0) {
                    for (int r = 0; r < p.rows; r++) {
                        int idx = r * p.cols + c;
                        if (p.tentAllowed(r, c) && !grassFixed[idx] && !tentFixed[idx]) {
                            grassFixed[idx] = true;
                            changed = true;
                            if (!eliminate(idx, treeOpts, cellTrees)) return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    /** 把某格从所有树的候选域中剔除；若某树候选被清空则冲突 */
    private static boolean eliminate(int cell,
                                     java.util.List<java.util.List<Integer>> treeOpts,
                                     java.util.List<java.util.List<Integer>> cellTrees) {
        for (int t : cellTrees.get(cell)) {
            treeOpts.get(t).remove(Integer.valueOf(cell));
            if (treeOpts.get(t).isEmpty()) return false;
        }
        return true;
    }
}

纯传播能解掉绝大多数入门与中等难度帐篷题（约 60%~80% 的格子被直接确定），但剩下的部分必须靠搜索或匹配。

四、解法二：二分图完美匹配

把问题重新建模：左侧是树集合，右侧是候选格集合，边表示”这棵树可以用这个格当帐篷”。要求的是一组完美匹配（每棵树都配上不同的格）且满足行列提示数。

Hopcroft-Karp 是求最大二分匹配的最优算法，复杂度 O(E√V)。帐篷谜题里 V ≤ 100，E ≤ 4V，所以几乎瞬间完成。

public final class BipartiteMatching {
    private final java.util.List<java.util.List<Integer>> adj;  // 树 -> 候选格
    private final int[] matchCell;   // 格 -> 配对的树，-1 表示未匹配
    private final int[] matchTree;   // 树 -> 配对的格
    private final int[] dist;

    public BipartiteMatching(java.util.List<java.util.List<Integer>> adj, int cellCount) {
        this.adj = adj;
        this.matchCell = new int[cellCount];
        this.matchTree = new int[adj.size()];
        this.dist = new int[adj.size()];
        java.util.Arrays.fill(matchCell, -1);
        java.util.Arrays.fill(matchTree, -1);
    }

    /** 返回匹配数 */
    public int solve() {
        int matching = 0;
        while (true) {
            // 1) BFS 分层：从所有未匹配的树出发
            java.util.ArrayDeque<Integer> q = new java.util.ArrayDeque<>();
            for (int t = 0; t < adj.size(); t++) {
                if (matchTree[t] == -1) { dist[t] = 0; q.add(t); }
                else dist[t] = Integer.MAX_VALUE;
            }
            boolean found = false;
            while (!q.isEmpty()) {
                int t = q.poll();
                for (int cell : adj.get(t)) {
                    int nt = matchCell[cell];
                    if (nt == -1) {
                        found = true;   // 找到增广路终点
                    } else if (dist[nt] == Integer.MAX_VALUE) {
                        dist[nt] = dist[t] + 1;
                        q.add(nt);
                    }
                }
            }
            if (!found) return matching;

            // 2) DFS 沿分层找多条增广路
            for (int t = 0; t < adj.size(); t++) {
                if (matchTree[t] == -1 && dfs(t)) matching++;
            }
        }
    }

    private boolean dfs(int t) {
        for (int cell : adj.get(t)) {
            int nt = matchCell[cell];
            if (nt == -1 || (dist[nt] == dist[t] + 1 && dfs(nt))) {
                matchTree[t] = cell;
                matchCell[cell] = t;
                return true;
            }
        }
        dist[t] = Integer.MAX_VALUE;
        return false;
    }
}

Hopcroft-Karp 给出的是”任一”完美匹配，但没有维护行列提示数。解决办法是把行列约束变成容量约束，用网络流替代匹配：

• 源点 → 每棵树（容量 1）
• 树 → 候选格（容量 1）
• 格 → 所在行节点（容量 1）、格 → 所在列节点（容量 1）——不行，一个格不能同时走两条

正确建模是二部 + 容量：树 → 格 → 行/列，但需要给每格加”分裂点”。更简洁的方式是用行列提示数作为附加的匹配目标，逐行贪心配置后再检验。实践中帐篷谜题更常用的做法是：

1. 用 Hopcroft-Karp 求一个基础完美匹配；
2. 检查行列提示数，若某行超出则收缩该行候选域，重新求解；
3. 迭代直到行列均满足。

这是”约束传播 + 匹配 + 可行性修复”的混合框架，收敛速度远好于从头搜索。

五、完整求解流程

public final class TentsSolver {
    public static Cell[][] solve(Puzzle p) {
        int total = p.rows * p.cols;
        boolean[] tentFixed = new boolean[total];
        boolean[] grassFixed = new boolean[total];
        int[] rowRemain = p.rowHint.clone();
        int[] colRemain = p.colHint.clone();

        java.util.List<java.util.List<Integer>> treeOpts = Domains.tentOptionsForTrees(p);
        java.util.List<java.util.List<Integer>> cellTrees = Domains.treesForCell(p);

        if (!Propagator.propagate(p, treeOpts, cellTrees, tentFixed, grassFixed,
                                  rowRemain, colRemain)) {
            throw new IllegalStateException("题目无解（传播阶段冲突）");
        }

        // 剩余用匹配确定
        BipartiteMatching bm = new BipartiteMatching(treeOpts, total);
        int matched = bm.solve();
        if (matched != treeOpts.size()) {
            throw new IllegalStateException("不存在完美匹配，题目无解");
        }

        // 输出棋盘：树保留，匹配到的格标帐篷，其余标草地
        Cell[][] out = new Cell[p.rows][p.cols];
        for (int r = 0; r < p.rows; r++) {
            for (int c = 0; c < p.cols; c++) {
                out[r][c] = (p.grid[r][c] == Cell.TREE) ? Cell.TREE : Cell.GRASS;
            }
        }
        for (int t = 0; t < treeOpts.size(); t++) {
            int cell = bm.matchTree[t];
            if (cell >= 0) out[cell / p.cols][cell % p.cols] = Cell.TENT;
        }
        return out;
    }
}

匹配完成后还必须校验一条匹配算法本身管不到的约束：任意两顶帐篷不能落在彼此的 8 邻域内。若出现这种冲突，说明该匹配不合法，需要把冲突格从候选域中剔除后重求。这是帐篷谜题区别于标准二分匹配的唯一分叉点，工程上通常靠”先传播、再匹配、冲突则回溯重匹配”的三段式处理，实际收敛很快，少数题才需要两到三轮迭代。

六、复杂度对比与工程建议

三条实战建议：

1. 先传播再匹配。传播能砍掉大量候选，后续匹配规模骤减。反过来先匹配再传播，往往要在巨型匹配上反复修补，得不偿失。
2. 提示数是”最强约束”。行/列提示为 0 时该行全草地，为满值时该行全帐篷，这两条规则的剪枝效率远高于任何启发式搜索。
3. 八邻域互斥要提前维护。不要等到最后校验，一旦确定帐篷就立刻封锁周边 8 格，这相当于免费的约束传播。

帐篷谜题的迷人之处在于：它表面是”画画”，实际是”配对”。一旦你把”每棵树配一顶帐篷”识别为完美匹配，整道题就从指数搜索降级为多项式时间——这种”重新建模换来复杂度跃迁”的体验，正是算法训练里最有价值的一课。