每日算法 — 使用java实现扫雷：整数规划松弛与分支定界求解

一、游戏场景：扫雷的”边界格”是一道 0-1 规划

扫雷（Minesweeper）的规则人人皆知：点开格子，数字代表周围 8 格的地雷数。新手靠直觉点，高手靠推理排雷——但真正的分水岭出现在信息不完全的时刻：当所有逻辑推理（单格确定、1-2-1 模式、1-2-2-1 模式）都用尽，仍有一批”边界格”无法确定时，该点哪一个？

这个问题其实不是猜谜，而是一道标准的整数线性规划（ILP）：

• 每个未开格 c 有一个 0-1 变量 x_c，表示”这格是雷”；
• 每个已开数字格 n 给出一条等式约束 Σ_{c ∈ N(n)} x_c = k_n，其中 N(n) 是 n 周围未开格集合，k_n 是显示的数字减去已确认的雷数；
• 目标函数可以有多解：求”某格能否取 0 / 能否取 1″以判定安全格，或求某格的取值概率。

本文用 Java 实现完整求解链：0-1 模型 → 线性松弛（LP）→ 两阶段单纯形 → 分支定界（B&B）→ 安全格判定 → 风险评估，并用手写暴力枚举作为对拍基准。这套方法是真实扫雷求解器的核心骨架。

二、从棋盘到约束系统

2.1 三类格子

不是所有格子都要进模型：

1. 已开格（opened）：已知非雷，仅供产生约束；
2. 已标记格（flagged）：已知是雷，固定 x = 1，不产生变量；
3. 未开未标记格（covered）：候选变量。其中只有与某个已开数字格相邻的才值得建模（称为 frontier，边界格），孤立格子与任何约束无关。

对每个已开数字格 n：

remain_n = digit(n) - (n 周围已标记的雷数)
N(n)     = n 周围未开且未标记的格子
约束:      Σ_{c ∈ N(n)} x_c = remain_n

如果 remain_n < 0 说明标记矛盾；N(n) 为空而 remain_n > 0 说明局面矛盾——这两种情况都应当立即抛出异常，而不是继续求解。

2.2 变量压缩：为什么必须做

一个中级局面的边界格常有 20～60 个，约束 15～40 条，直接暴力 2^40 枚举必然超时。但约束是局部的：边界格按约束图自然分裂成若干互不相交的小组件，每个组件往往只有 5～12 个变量。分组求解是这类问题的第一个工程杠杆。

2.3 三条可判定的结论

对每个组件分别求解，可以得到三类信息：

第二类必须用精确整数求解（分支定界）。第三类如果允许近似，直接用 LP 松弛即可——这就是本文两条路线的由来：松弛定界、分支定界定论。

三、线性松弛与两阶段单纯形

3.1 松弛

把 x_c ∈ {0,1} 放宽为 0 ≤ x_c ≤ 1，得到 LP：

min c^T x
s.t. A x = b        （每个数字格一条等式）
     x_c + s_c = 1  （上界转等式，s_c ≥ 0 为松弛变量）
     x ≥ 0, s ≥ 0

LP 最优值给出 ILP 最优值的界；而松弛解里的 x_c 值可以当作该格是雷的近似概率——约束越”尖”，这个近似越准。

3.2 两阶段单纯形

等式约束的 LP 需要初始可行基。标准做法：第一阶段（Phase I）给每条等式加人工变量 a_i ≥ 0，先最小化 Σ a_i；若最小值为 0，则得到可行基，进入第二阶段（Phase II）优化真实目标。入基按 Bland 规则（选下标最小的负检验数）以避免退化循环。

package com.algodaily.minesweeper.ilp;

import java.util.Arrays;

/**
 * 两阶段单纯形：求解 min c^T x，s.t. A x = b，x >= 0。
 * 行数 m 即约束数，列数 n 即决策变量数；b 必须非负（调用方负责归一化）。
 */
public final class Simplex {

    private static final double EPS = 1e-9;
    private static final double INF = 1e100;

    private final int m;
    private final int n;
    private final double[][] a;
    private final double[] b;
    private final double[] c;

    public Simplex(double[][] aMat, double[] rhs, double[] cost) {
        this.m = rhs.length;
        this.n = cost.length;
        this.a = new double[m][];
        for (int i = 0; i < m; i++) this.a[i] = Arrays.copyOf(aMat[i], aMat[i].length);
        this.b = Arrays.copyOf(rhs, rhs.length);
        this.c = Arrays.copyOf(cost, cost.length);
    }

    /** 求解结果 */
    public static final class Result {
        public final boolean feasible;
        public final double objective;
        public final double[] x;

        Result(boolean feasible, double objective, double[] x) {
            this.feasible = feasible;
            this.objective = objective;
            this.x = x;
        }
    }

    public Result solve() {
        // 变量布局：[0,n) 原始变量；[n,n+m) 人工变量；最后一列存右端项
        int cols = n + m + 1;
        double[][] t = new double[m][cols];
        for (int i = 0; i < m; i++) {
            if (b[i] < -EPS) return new Result(false, 0.0, new double[n]); // 右端为负，无可行解
            for (int j = 0; j < n; j++) t[i][j] = a[i][j];
            t[i][n + i] = 1.0;             // 人工变量作初始基
            t[i][cols - 1] = b[i];
        }
        int[] basis = new int[m];
        for (int i = 0; i < m; i++) basis[i] = n + i;

        // ---------- Phase I：最小化人工变量之和 ----------
        double[] phase1 = new double[cols - 1];
        for (int i = 0; i < m; i++) phase1[n + i] = 1.0;
        iterate(t, basis, phase1, cols, true);

        double artificialSum = 0.0;
        for (int i = 0; i < m; i++) artificialSum += t[i][cols - 1] * phase1[basis[i]];
        if (artificialSum > 1e-7) return new Result(false, 0.0, new double[n]);

        // 把仍留在基里的人工变量换出去
        for (int i = 0; i < m; i++) {
            if (basis[i] >= n) {
                int pivotCol = -1;
                for (int j = 0; j < n; j++) {
                    if (Math.abs(t[i][j]) > 1e-7) { pivotCol = j; break; }
                }
                if (pivotCol == -1) {
                    for (int j = 0; j < cols; j++) t[i][j] = 0.0; // 冗余约束，整行清零
                } else {
                    pivot(t, basis, i, pivotCol, cols);
                }
            }
        }

        // ---------- Phase II：最小化真实目标 ----------
        double[] phase2 = new double[cols - 1];
        for (int j = 0; j < n; j++) phase2[j] = c[j];
        iterate(t, basis, phase2, cols, false);

        double[] x = new double[n];
        for (int i = 0; i < m; i++) {
            if (basis[i] < n) x[basis[i]] = t[i][cols - 1];
        }
        double obj = 0.0;
        for (int j = 0; j < n; j++) obj += c[j] * x[j];
        return new Result(true, obj, x);
    }

    /** 反复换基（Bland 规则）直到对偶可行 */
    private void iterate(double[][] t, int[] basis, double[] cost, int cols, boolean allowUnbounded) {
        for (int step = 0; step < 20000; step++) {
            // 检验数 reduced_j = c_j - c_B^T B^-1 A_j
            double[] reduced = new double[cols - 1];
            for (int j = 0; j < cols - 1; j++) {
                reduced[j] = cost[j];
                for (int i = 0; i < m; i++) reduced[j] -= cost[basis[i]] * t[i][j];
            }

            int enter = -1;
            for (int j = 0; j < cols - 1; j++) {
                if (reduced[j] < -EPS) { enter = j; break; }
            }
            if (enter == -1) return; // 已最优

            int leave = -1;
            double bestRatio = INF;
            for (int i = 0; i < m; i++) {
                if (t[i][enter] > EPS) {
                    double ratio = t[i][cols - 1] / t[i][enter];
                    if (ratio < bestRatio - EPS) { bestRatio = ratio; leave = i; }
                }
            }
            if (leave == -1) {
                if (allowUnbounded) return; // 第一阶段不会无界
                throw new IllegalStateException("LP 无界");
            }
            pivot(t, basis, leave, enter, cols);
        }
        throw new IllegalStateException("单纯形迭代超限，可能存在退化");
    }

    /** 以 (row, col) 为枢轴换基 */
    private void pivot(double[][] t, int[] basis, int row, int col, int cols) {
        double pv = t[row][col];
        for (int j = 0; j < cols; j++) t[row][j] /= pv;
        for (int i = 0; i < m; i++) {
            if (i == row) continue;
            double f = t[i][col];
            if (Math.abs(f) < EPS) continue;
            for (int j = 0; j < cols; j++) t[i][j] -= f * t[row][j];
        }
        basis[row] = col;
    }
}

代价是每次换基 O(m·cols)，总时间 O(迭代数 × m × cols)。对扫雷组件（m ≤ 40、cols ≤ 80）完全够用；但不适合大棋盘——高性能求解器会用 SAT/CDCL 或对偶单纯形热启动，而不是每个节点重建表。

四、分支定界：从松弛到定论

4.1 框架

LP 松弛给出界。若松弛解里所有变量都已是 0 或 1，则它本身就是 ILP 最优解，直接采用；否则选一个分数变量 x_c = 0.37 分两支：

• 分支 A：x_c = 0（这格安全）；
• 分支 B：x_c = 1（这格是雷）。

每分支重解 LP，用当前最优整数解作上界剪枝。但对扫雷，我们真正需要的是“某格能否取 0 / 能否取 1”，所以更高效的写法是可行性分支定界：只判定”在附加约束下是否可行”，不做目标优化。可行性检查比最优化便宜，且直接给出确定性结论。

4.2 Java 实现

package com.algodaily.minesweeper.ilp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 0-1 整数规划求解器：LP 松弛 + 深度优先分支定界。
 * 支持两种模式：最优化（solve）与纯可行性判定（isFeasible）。
 */
public final class BranchAndBound {

    /** 模型：min c^T x，s.t. A x = b，x ∈ {0,1}^n */
    public static final class Model {
        public final int n;
        public final List<double[]> rows = new ArrayList<>();
        public final List<Double> rhs = new ArrayList<>();
        public final double[] cost;

        public Model(int n, double[] cost) {
            this.n = n;
            this.cost = cost;
        }

        public void addRow(double[] coef, double r) {
            if (coef.length != n) throw new IllegalArgumentException("系数维度不匹配");
            rows.add(coef);
            rhs.add(r);
        }
    }

    public static final class Answer {
        public final boolean feasible;
        public final double objective;
        public final double[] x;

        Answer(boolean feasible, double objective, double[] x) {
            this.feasible = feasible;
            this.objective = objective;
            this.x = x;
        }
    }

    private static final double INF = Double.POSITIVE_INFINITY;

    private final Model model;
    private Answer incumbent = new Answer(false, INF, null);

    public BranchAndBound(Model model) { this.model = model; }

    /** 最优化：返回最优整数解 */
    public Answer solve() {
        double[] fixed = new double[model.n];
        Arrays.fill(fixed, Double.NaN); // NaN 表示未固定
        dfsOpt(fixed);
        return incumbent;
    }

    /** 纯可行性：在给定固定条件下是否存在整数解 */
    public boolean isFeasible(double[] fixed) {
        return dfsFeasible(fixed.clone());
    }

    // ---------- LP 松弛 ----------

    /**
     * 构造并求解一次 LP 松弛。上界 x_j <= 1 通过 x_j + s_j = 1 转成等式，
     * 因此列数为 2n（原始变量 + 上界松弛变量）。
     */
    private Answer relax(double[] fixed) {
        int n = model.n;
        int rowCount = model.rows.size() + n;
        double[][] a = new double[rowCount][2 * n];
        double[] b = new double[rowCount];
        double[] cost = new double[2 * n];

        System.arraycopy(model.cost, 0, cost, 0, n);

        // 1) 数字格等式约束；已固定变量移到右端
        for (int i = 0; i < model.rows.size(); i++) {
            double[] coef = model.rows.get(i);
            double r = model.rhs.get(i);
            for (int j = 0; j < n; j++) {
                if (Double.isNaN(fixed[j])) {
                    a[i][j] = coef[j];
                } else {
                    r -= coef[j] * fixed[j];
                }
            }
            b[i] = r;
        }

        // 2) 上界约束 x_j + s_j = 1
        for (int j = 0; j < n; j++) {
            int r = model.rows.size() + j;
            if (Double.isNaN(fixed[j])) {
                a[r][j] = 1.0;
                a[r][n + j] = 1.0;
                b[r] = 1.0;
            } else {
                if (fixed[j] < -1e-9 || fixed[j] > 1 + 1e-9) {
                    return new Answer(false, INF, null);
                }
                b[r] = 1.0 - fixed[j]; // 相当于 0 = 1 - fixed_j，即 0 <= x <= 1 已满足
            }
        }

        Simplex.Result lp = new Simplex(a, b, cost).solve();
        if (!lp.feasible) return new Answer(false, INF, null);
        return new Answer(true, lp.objective, lp.x);
    }

    // ---------- 可行性分支定界 ----------

    private boolean dfsFeasible(double[] fixed) {
        Answer lp = relax(fixed);
        if (!lp.feasible) return false;                 // 松弛不可行 => 整数不可行
        int col = pickFractional(lp.x, fixed);
        if (col < 0) return true;                       // 松弛解全整数 => 可行

        fixed[col] = 0.0;                               // 先试"安全"
        if (dfsFeasible(fixed)) { fixed[col] = Double.NaN; return true; }
        fixed[col] = 1.0;
        boolean ok = dfsFeasible(fixed);
        fixed[col] = Double.NaN;
        return ok;
    }

    // ---------- 最优化分支定界 ----------

    private void dfsOpt(double[] fixed) {
        Answer lp = relax(fixed);
        if (!lp.feasible) return;
        if (incumbent.feasible && lp.objective > incumbent.objective - 1e-9) return; // 剪枝

        int col = pickFractional(lp.x, fixed);
        if (col < 0) {
            double obj = 0.0;
            for (int j = 0; j < model.n; j++) obj += model.cost[j] * lp.x[j];
            if (!incumbent.feasible || obj < incumbent.objective) {
                incumbent = new Answer(true, obj, lp.x.clone());
            }
            return;
        }
        fixed[col] = 0.0;
        dfsOpt(fixed);
        fixed[col] = 1.0;
        dfsOpt(fixed);
        fixed[col] = Double.NaN;
    }

    /** 返回第一个分数变量的下标；全整数时返回 -1 */
    private int pickFractional(double[] x, double[] fixed) {
        for (int j = 0; j < model.n; j++) {
            if (Double.isNaN(fixed[j]) && x[j] > 1e-6 && x[j] < 1.0 - 1e-6) return j;
        }
        return -1;
    }
}

五、拼装成扫雷求解器

5.1 棋盘视图

package com.algodaily.minesweeper;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 棋盘视图。取值约定：
 *  -3 未开且未标记（covered）
 *  -2 已标记为雷（flag）
 *   0..8 已开且显示该数字
 */
public final class Board {
    public static final int COVERED = -3;
    public static final int FLAG = -2;

    public final int rows, cols;
    public final int[][] cell;

    /** 8 邻域偏移 */
    public static final int[][] DIRS = {
            {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
    };

    public Board(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.cell = new int[rows][cols];
        for (int i = 0; i < rows; i++) Arrays.fill(cell[i], COVERED);
    }

    public boolean inBounds(int r, int c) { return r >= 0 && r < rows && c >= 0 && c < cols; }
    public boolean isCovered(int r, int c) { return cell[r][c] == COVERED; }
    public boolean isFlagged(int r, int c) { return cell[r][c] == FLAG; }
    public boolean isOpened(int r, int c) { return cell[r][c] >= 0; }

    public List<int[]> neighbors(int r, int c) {
        List<int[]> res = new ArrayList<>(8);
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (inBounds(nr, nc)) res.add(new int[]{nr, nc});
        }
        return res;
    }
}

5.2 约束抽取与组件拆分

package com.algodaily.minesweeper;

import com.algodaily.minesweeper.ilp.BranchAndBound;
import com.algodaily.minesweeper.ilp.Simplex;

import java.util.*;

/**
 * 扫雷求解器：
 *  1) 抽取边界变量与数字约束
 *  2) 按约束图连通性拆成独立组件（并查集）
 *  3) 每组件用 ILP 判定"必雷 / 必安全"
 *  4) 用 LP 松弛解作为每格是雷的概率近似，挑最低风险格
 */
public final class MinesweeperSolver {

    /** 组件：局部变量表 + 局部等式约束 */
    public static final class Component {
        public final List<int[]> cells = new ArrayList<>();      // {r, c}
        public final List<double[]> rows = new ArrayList<>();    // 系数行
        public final List<Double> rhs = new ArrayList<>();       // 右端项

        public int size() { return cells.size(); }

        public int indexOf(int r, int c) {
            for (int k = 0; k < cells.size(); k++) {
                int[] p = cells.get(k);
                if (p[0] == r && p[1] == c) return k;
            }
            return -1;
        }
    }

    private final Board board;
    public final List<Component> components = new ArrayList<>();

    /** 每格的雷概率：-1 表示未参与建模 */
    public final double[][] risk;
    /** 每格判定结论：1 必雷、0 必安全、-1 未知 */
    public final int[][] verdict;

    public MinesweeperSolver(Board board) {
        this.board = board;
        this.risk = new double[board.rows][board.cols];
        this.verdict = new int[board.rows][board.cols];
        for (int r = 0; r < board.rows; r++) {
            Arrays.fill(risk[r], -1.0);
            Arrays.fill(verdict[r], -1);
        }
        buildConstraints();
    }

    // ---------- 步骤 1：约束抽取 + 并查集分组 ----------

    private void buildConstraints() {
        // 每条约束先以 (unknownCells, remain) 形式收集
        List<List<int[]>> consCells = new ArrayList<>();
        List<Double> consRhs = new ArrayList<>();

        for (int r = 0; r < board.rows; r++) {
            for (int c = 0; c < board.cols; c++) {
                if (!board.isOpened(r, c)) continue;
                int remain = board.cell[r][c];
                List<int[]> unknown = new ArrayList<>();
                for (int[] nb : board.neighbors(r, c)) {
                    if (board.isFlagged(nb[0], nb[1])) remain--;
                    else if (board.isCovered(nb[0], nb[1])) unknown.add(nb);
                }
                if (remain < 0) throw new IllegalStateException("标记矛盾 @ (" + r + "," + c + ")");
                if (unknown.isEmpty()) {
                    if (remain > 0) throw new IllegalStateException("约束矛盾 @ (" + r + "," + c + ")");
                    continue;
                }
                consCells.add(unknown);
                consRhs.add((double) remain);
            }
        }

        // 用并查集把出现在同一约束里的格子连起来
        Map<Long, Integer> idOf = new HashMap<>();
        for (List<int[]> cons : consCells) {
            for (int[] p : cons) idOf.computeIfAbsent(key(p[0], p[1]), k -> idOf.size());
        }
        int total = idOf.size();
        int[] uf = new int[total];
        for (int i = 0; i < total; i++) uf[i] = i;
        for (List<int[]> cons : consCells) {
            int first = find(uf, idOf.get(key(cons.get(0)[0], cons.get(0)[1])));
            for (int i = 1; i < cons.size(); i++) {
                union(uf, first, find(uf, idOf.get(key(cons.get(i)[0], cons.get(i)[1]))));
            }
        }

        // 按根分组，建立 Component
        Map<Integer, Component> byRoot = new LinkedHashMap<>();
        Map<Long, Component> compOfCell = new HashMap<>();
        for (Map.Entry<Long, Integer> e : idOf.entrySet()) {
            int root = find(uf, e.getValue());
            Component comp = byRoot.computeIfAbsent(root, k -> new Component());
            int r = (int) (e.getKey() / 1000L);
            int c = (int) (e.getKey() % 1000L);
            comp.cells.add(new int[]{r, c});
            compOfCell.put(e.getKey(), comp);
        }
        for (Component comp : byRoot.values()) components.add(comp);

        // 把约束翻译成局部系数行
        for (int i = 0; i < consCells.size(); i++) {
            List<int[]> cons = consCells.get(i);
            Component comp = compOfCell.get(key(cons.get(0)[0], cons.get(0)[1]));
            double[] row = new double[comp.size()];
            for (int[] p : cons) row[comp.indexOf(p[0], p[1])] = 1.0;
            comp.rows.add(row);
            comp.rhs.add(consRhs.get(i));
        }
    }

    private static long key(int r, int c) { return r * 1000L + c; }

    private static int find(int[] uf, int x) {
        while (uf[x] != x) { uf[x] = uf[uf[x]]; x = uf[x]; }
        return x;
    }

    private static void union(int[] uf, int a, int b) {
        if (a != b) uf[a] = b;
    }

    // ---------- 步骤 2：单组件判定 ----------

    /** 判定该组件中每格的状态，并把概率写入 risk */
    public void analyze(Component comp) {
        int n = comp.size();
        BranchAndBound.Model model = new BranchAndBound.Model(n, new double[n]);
        for (int i = 0; i < comp.rows.size(); i++) model.addRow(comp.rows.get(i), comp.rhs.get(i));

        BranchAndBound solver = new BranchAndBound(model);
        double[] fixed = new double[n];

        // ① 可行性分支定界：逐格判定能否取 0 / 能否取 1
        for (int k = 0; k < n; k++) {
            int[] pos = comp.cells.get(k);

            Arrays.fill(fixed, Double.NaN);
            fixed[k] = 0.0;
            if (!solver.isFeasible(fixed)) {
                verdict[pos[0]][pos[1]] = 1;    // 不能取 0 => 必是雷
                risk[pos[0]][pos[1]] = 1.0;
                continue;
            }

            Arrays.fill(fixed, Double.NaN);
            fixed[k] = 1.0;
            if (!solver.isFeasible(fixed)) {
                verdict[pos[0]][pos[1]] = 0;    // 不能取 1 => 必安全
                risk[pos[0]][pos[1]] = 0.0;
                continue;
            }

            verdict[pos[0]][pos[1]] = -1;       // 两种取值都可行 => 无法确定
        }

        // ② LP 松弛解作为未定格的概率近似
        double[] approx = relaxProbability(comp);
        for (int k = 0; k < n; k++) {
            int[] pos = comp.cells.get(k);
            if (verdict[pos[0]][pos[1]] == -1) {
                risk[pos[0]][pos[1]] = approx[k];
            }
        }
    }

    /** 解 LP 松弛（目标全 0），返回各变量取值作为概率近似 */
    private double[] relaxProbability(Component comp) {
        int n = comp.size();
        int rowCount = comp.rows.size() + n;
        double[][] a = new double[rowCount][2 * n];
        double[] b = new double[rowCount];

        for (int i = 0; i < comp.rows.size(); i++) {
            System.arraycopy(comp.rows.get(i), 0, a[i], 0, n);
            b[i] = comp.rhs.get(i);
        }
        for (int j = 0; j < n; j++) {
            int r = comp.rows.size() + j;
            a[r][j] = 1.0;
            a[r][n + j] = 1.0;
            b[r] = 1.0;
        }

        Simplex.Result lp = new Simplex(a, b, new double[2 * n]).solve();
        double[] x = new double[n];
        if (lp.feasible) {
            for (int j = 0; j < n; j++) x[j] = Math.min(1.0, Math.max(0.0, lp.x[j]));
        }
        return x;
    }

    // ---------- 步骤 3：对外结论 ----------

    public List<int[]> safeCells() { return filter(0); }
    public List<int[]> mineCells() { return filter(1); }

    private List<int[]> filter(int v) {
        List<int[]> res = new ArrayList<>();
        for (int r = 0; r < board.rows; r++) {
            for (int c = 0; c < board.cols; c++) {
                if (board.isCovered(r, c) && verdict[r][c] == v) res.add(new int[]{r, c});
            }
        }
        return res;
    }

    /**
     * 推荐猜测：在所有未开格中取"雷概率最小"的那个。
     * 未参与建模的格子直接按全局雷密度估计（用已开数字反推的上界）。
     */
    public int[] bestGuess() {
        int[] best = null;
        double bestP = 2.0;
        for (int r = 0; r < board.rows; r++) {
            for (int c = 0; c < board.cols; c++) {
                if (!board.isCovered(r, c)) continue;
                double p = risk[r][c];
                if (p < 0) p = globalMineDensity(); // 视野外的格子按全局密度估计
                if (p < bestP) { bestP = p; best = new int[]{r, c}; }
            }
        }
        return best;
    }

    /** 由已知数字反推的雷密度下界（用于估计视野外格子） */
    public double globalMineDensity() {
        double known = 0, cells = 0;
        for (int r = 0; r < board.rows; r++) {
            for (int c = 0; c < board.cols; c++) {
                if (board.isOpened(r, c)) {
                    known += board.cell[r][c];
                    cells++;
                }
            }
        }
        return cells == 0 ? 0.2 : Math.min(1.0, known / (cells * 8.0));
    }
}

5.3 暴力枚举对拍

package com.algodaily.minesweeper;

import java.util.Arrays;

/**
 * 暴力枚举基准：枚举 2^n 个赋值，得出每格"必雷/必安全/未知"与可行解总数。
 * 仅用于小规模组件（n <= 22）的对拍。
 */
public final class BruteForceOracle {

    /** 返回每格状态：1 必雷、0 必安全、-1 未知；out[0] 写入可行解总数 */
    public static int[] analyze(MinesweeperSolver.Component comp, long[] out) {
        int n = comp.size();
        int[] state = new int[n]; // 2 表示尚未记录
        Arrays.fill(state, 2);
        long count = 0;

        for (long mask = 0; mask < (1L << n); mask++) {
            boolean ok = true;
            for (int i = 0; i < comp.rows.size(); i++) {
                double sum = 0.0;
                double[] row = comp.rows.get(i);
                for (int j = 0; j < n; j++) {
                    if (row[j] != 0.0 && ((mask >> j) & 1L) == 1L) sum += row[j];
                }
                if (Math.abs(sum - comp.rhs.get(i)) > 1e-9) { ok = false; break; }
            }
            if (!ok) continue;

            count++;
            for (int j = 0; j < n; j++) {
                int b = (int) ((mask >> j) & 1L);
                if (state[j] == 2) state[j] = b;
                else if (state[j] != b) state[j] = -1; // 两种取值都出现过
            }
        }
        if (out != null && out.length > 0) out[0] = count;
        return state;
    }
}

5.4 演示与随机对拍入口

package com.algodaily.minesweeper;

import java.util.List;
import java.util.Random;

/** 入口：先演示一个 1-2-1 局面，再随机对拍 200 个局面 */
public final class MinesweeperApp {

    public static void main(String[] args) {
        demo121();
        stressTest();
    }

    /** 经典 1-2-1 模式：中间数字 2 的两侧各一个 1，下方三格中必有中间的雷 */
    private static void demo121() {
        Board b = new Board(3, 5);
        // 第二行开出数字：1, 2, 1, 0, 0
        b.cell[1][0] = 1;
        b.cell[1][1] = 2;
        b.cell[1][2] = 1;
        b.cell[1][3] = 0;
        b.cell[1][4] = 0;

        MinesweeperSolver solver = new MinesweeperSolver(b);
        System.out.println("组件数 = " + solver.components.size());
        for (MinesweeperSolver.Component comp : solver.components) {
            System.out.println("  组件规模 = " + comp.size() + "，约束数 = " + comp.rows.size());
            solver.analyze(comp);
        }
        System.out.println("必安全格 = " + fmt(solver.safeCells()));
        System.out.println("必雷格   = " + fmt(solver.mineCells()));
        System.out.println("建议猜测 = " + fmtOne(solver.bestGuess()));
        new BoardView(b).printRisk(solver.risk);
    }

    private static String fmt(List<int[]> list) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < list.size(); i++) {
            sb.append("(").append(list.get(i)[0]).append(",").append(list.get(i)[1]).append(")");
            if (i + 1 < list.size()) sb.append(" ");
        }
        return sb.append("]").toString();
    }

    private static String fmtOne(int[] p) {
        return p == null ? "null" : "(" + p[0] + "," + p[1] + ")";
    }

    /** 随机局面：ILP 结论与暴力枚举逐格比对 */
    private static void stressTest() {
        Random rnd = new Random(20261101L);
        int mismatch = 0, compared = 0;

        for (int iter = 0; iter < 200; iter++) {
            int rows = 3 + rnd.nextInt(2), cols = 3 + rnd.nextInt(3);
            Board b = new Board(rows, cols);

            boolean[][] mine = new boolean[rows][cols];
            int mineCount = 0;
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (rnd.nextInt(100) < 18) { mine[r][c] = true; mineCount++; }
                }
            }
            if (mineCount == 0) continue;

            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (!mine[r][c] && rnd.nextInt(100) < 45) { // 开出约 45% 的非雷格
                        b.cell[r][c] = countNeighborMines(b, mine, r, c);
                    }
                }
            }

            MinesweeperSolver solver;
            try {
                solver = new MinesweeperSolver(b);
            } catch (RuntimeException ex) {
                continue; // 局面本身矛盾，跳过
            }

            for (MinesweeperSolver.Component comp : solver.components) {
                if (comp.size() == 0 || comp.size() > 20) continue; // 控制枚举规模
                solver.analyze(comp);
                long[] cnt = new long[1];
                int[] oracle = BruteForceOracle.analyze(comp, cnt);

                for (int k = 0; k < comp.size(); k++) {
                    int[] pos = comp.cells.get(k);
                    int expected = oracle[k];
                    if (expected == -1) continue; // 枚举也判定未知，不做比较
                    compared++;
                    if (solver.verdict[pos[0]][pos[1]] != expected) {
                        mismatch++;
                        System.out.println("不一致 cell=(" + pos[0] + "," + pos[1] + ")"
                                + " ilp=" + solver.verdict[pos[0]][pos[1]]
                                + " oracle=" + expected + " 解数=" + cnt[0]);
                    }
                }
            }
        }
        System.out.println("对拍格数 = " + compared + "，不一致 = " + mismatch);
    }

    private static int countNeighborMines(Board b, boolean[][] mine, int r, int c) {
        int cnt = 0;
        for (int[] d : Board.DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (b.inBounds(nr, nc) && mine[nr][nc]) cnt++;
        }
        return cnt;
    }
}

演示代码需要读取棋盘状态来打印概率矩阵，这里用一个只读的 BoardView 把内部字段封装起来，避免演示逻辑直接触碰 Board.cell：

package com.algodaily.minesweeper;

/** 棋盘的轻量访问器：只读暴露，避免演示代码直接触碰内部字段 */
public final class BoardView {

    private final Board board;

    public BoardView(Board board) { this.board = board; }

    public boolean isCovered(int r, int c) { return board.isCovered(r, c); }
    public boolean isFlagged(int r, int c) { return board.isFlagged(r, c); }
    public boolean isOpened(int r, int c) { return board.isOpened(r, c); }
    public int digit(int r, int c) { return board.cell[r][c]; }

    /** 打印雷概率矩阵（仅未开格） */
    public void printRisk(double[][] risk) {
        for (int r = 0; r < risk.length; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < risk[0].length; c++) {
                if (!isCovered(r, c)) { sb.append("   -   "); continue; }
                double p = risk[r][c];
                sb.append(p < 0 ? "   -   " : String.format(" %.3f ", p));
            }
            System.out.println(sb);
        }
    }
}

六、复杂度与工程取舍

工程取舍要点：

1. 别把整盘塞进一个 ILP。分组是决定生死的一步：30 变量的组件 LP 是毫秒级，300 变量的组件会把服务拖住。
2. 能算概率就别算整数。真正需要 B&B 的只有”必雷 / 必安全”的确定性判定；概率只需 LP 松弛解，代价低一到两个数量级。
3. LP 松弛解 ≠ 真实概率。约束交集”尖”的时候（多条等式只允许唯一解），LP 直接给出整数解，概率准确；约束宽松时会低估，想要精确概率得做组件内解计数（#P 问题），这也是真实求解器对小组件用枚举、对大组件用采样的原因。
4. 猜测价值不止概率。概率 0.3 的格子猜中后可能连锁展开十几格，概率 0.2 的格子可能一无所获。把”展开面积期望”纳入目标，就从”生存率最大化”换成了”收益最大化”。

七、这套方法还能用在哪

扫雷只是”部分信息约束下求可行域“的漂亮外衣。同一套 LP + B&B 骨架可以平移到：

• 数织（Nonogram）：行列约束是典型 0-1 覆盖，变量是每个像素，约束是连续段长度；
• 数独唯一性验证：判断盘面是否有唯一解，等价于检测是否存在两个不同整数解；
• 排班 / 装箱：现实业务里的整数规划几乎都是同一个模板——松弛给界、分支定界收敛、少量变量靠枚举兜底。

最值得记住的一条经验：“不确定”不等于”只能猜”。把局面写成一堆 0-1 约束之后，绝大部分”看起来要猜”的格子其实是可判定的；真正的赌局只发生在所有约束都宽松到无法区分的那一小片区域。