一、从”猜雷”到”算雷”
扫雷的难点从来不是标数字，而是面对一片未揭开的格子时判断”哪一格是雷的概率最低”。玩家凭直觉点，AI 需要给出一个可计算的数字。
多数扫雷求解器走到”局部约束传播”就停了：某个数字周围已确定几颗雷、几格安全，就标记一下。这套规则能解掉大部分简单局面，但一旦进入边界上的模糊区域——两三个数字互相牵制、剩余雷数又不确定——规则法就失效，只能靠概率排序去赌。
要真的”算”出来，需要一种能处理耦合约束、并且把全局剩余雷数也纳入的精确推理方法。本文用桶消元（Bucket Elimination）——变量消元在因子图上的经典实现——求解边界概率。它不靠采样、不做近似，给出的是数学上的精确边缘概率。
二、把棋盘翻译成因子图
只考虑边界格（frontier）：未揭开、且至少与一个已揭示数字相邻的格子。其余未揭开格与任何数字都不相邻，其概率只由剩余雷数决定，可以最后单独按组合数补齐。
- 每个边界格是一个二元变量 x_i ∈ {0,1}，1 表示有雷；
- 每个已揭示的数字格 c（值为 v）产生一个线索因子：邻域内未揭开边界变量之和等于 v；
- 全局剩余雷数 M 作为归一化条件参与最后一步计算。
于是”求解概率”等价于求条件边缘分布 P(x_i = 1 | 全部线索, 总雷数 = M)。朴素做法要枚举 2^n 种赋值，n 稍大就爆炸。桶消元的价值在于：按变量顺序逐个”消去”，每步只处理当前变量及其活跃邻居，复杂度从指数级 n 降到指数级诱导宽度 w。
三、桶消元的三步循环
算法本体极其简洁：
- 选一个待消去的变量 x；
- 把所有提到 x 的因子放进一个”桶”，相乘得到一个联合因子；
- 对 x 求和（sum-out），得到一个新因子放回因子池。
关键洞察是：被消去的变量不会再出现在后续计算中，所以每步只需处理”当前变量 + 活跃邻居”。扫雷的边界图通常是链状或小团块，诱导宽度常为 2~4，计算量随 n 近似线性增长，只随宽度指数增长。
顺序至关重要。工程上用 min-fill 启发式：每次挑”消去后需要在邻居间新增最少边”的变量。新增边就是未来的计算代价，min-fill 直接把这个代价压到最小。
四、把全局雷数藏进多项式
只做局部消元会漏掉”全局剩余雷数”，得到的是无视总量的边缘概率。补上它有一个很漂亮的技巧：让每个因子值不是标量，而是关于雷数的多项式。
规则只有两条：
- 因子相乘 → 多项式卷积（雷数相加）；
- 消去变量 x → 取 x=0 那一半不动，x=1 那一半系数右移一位（雷数 +1），两者相加。
这里有个极易踩的坑，值得单独强调：线索因子本身必须是指示函数，常数项为 1，不能把”邻域雷数”写进多项式。因为同一个变量会被多个线索因子共享，若每个因子都自带雷数计数，这颗雷就会被重复累加。正确的做法是：线索因子只回答”这个赋值合不合法”，雷数只在消元那一刻累计一次。这个坑我在实现时踩过，靠穷举对照才发现——这也说明精确推理必须配自校验。
消元结束后，若得到只含目标变量 x_i 的因子，其系数含义是：
val[1][c] = "x_i 为雷，其余边界变量共 c 颗雷"的权重
val[0][c] = "x_i 安全，其余边界变量共 c 颗雷"的权重
再补上非边界未知格（共 D 个）的组合权重 C(D, M−c)，条件概率一步得出：
P(x_i=1 | M) ∝ Σ_c val[1][c] · C(D, M−1−c)
P(x_i=0 | M) ∝ Σ_c val[0][c] · C(D, M−c)
归一化即可。这条式子把”局部约束”与”全局计数”缝在了一起，而且没有引入任何额外的计数变量。
五、Java 完整实现
单文件可运行：javac MinesweeperBucketElimination.java && java MinesweeperBucketElimination。
import java.util.*;
/**
* 扫雷边界精确概率求解：因子图 + 桶消元（变量消元）
*
* 核心思想：
* 1) 每个未揭开的边界格是一个二元变量 x_i（1=有雷）；
* 2) 每个已揭示的数字格是一个"指示因子"，只允许邻域雷数等于该数字的赋值；
* 3) 变量用"关于雷数的多项式"承载：消去 x 时，x=0 贡献 z^0，x=1 贡献 z^1，
* 因此消元结束后的系数直接就是"该赋值下总雷数"的计数分布；
* 4) 再对非边界未知格补上组合权重 C(deep, M-c)，即得精确边缘概率。
*/
public class MinesweeperBucketElimination {
static final int UNKNOWN = -1;
/** 边界变量数 N：同时作为多项式次数上限（最多 N 颗雷） */
static int N = 0;
/* ===================== 因子 ===================== */
static final class Factor {
final int[] vars; // 变量编号，升序
final double[][] val; // val[mask][c]：掩码 mask 下总雷数为 c 的权重
Factor(int[] vars, double[][] val) {
this.vars = vars;
this.val = val;
}
boolean contains(int v) {
for (int x : vars) if (x == v) return true;
return false;
}
int posOf(int v) {
for (int i = 0; i < vars.length; i++) if (vars[i] == v) return i;
return -1;
}
/** 线索因子：邻域雷数恰为 mines 时为 1，否则为 0；多项式只占常数项 */
static Factor clue(int[] vs, int mines) {
double[][] v = new double[1 << vs.length][N + 1];
for (int m = 0; m < v.length; m++)
if (Integer.bitCount(m) == mines) v[m][0] = 1.0;
return new Factor(vs, v);
}
}
static int[] posArray(int[] union, int[] sub) {
int[] p = new int[sub.length];
for (int i = 0; i < sub.length; i++) {
p[i] = -1;
for (int j = 0; j < union.length; j++)
if (union[j] == sub[i]) { p[i] = j; break; }
}
return p;
}
static int project(int mask, int[] pos) {
int r = 0;
for (int i = 0; i < pos.length; i++)
if (pos[i] >= 0 && (mask & (1 << pos[i])) != 0) r |= 1 << i;
return r;
}
/** 在 pos 位插入一个比特，其余比特相对顺序不变 */
static int insertBit(int mask, int pos, int bit) {
int low = mask & ((1 << pos) - 1);
int high = mask >>> pos;
return low | (bit << pos) | (high << (pos + 1));
}
/** 因子相乘：连接变量表 + 多项式卷积（次数截断到 N） */
static Factor multiply(Factor a, Factor b) {
TreeSet<Integer> set = new TreeSet<>();
for (int v : a.vars) set.add(v);
for (int v : b.vars) set.add(v);
int[] vars = new int[set.size()];
int p = 0;
for (int v : set) vars[p++] = v;
int[] pa = posArray(vars, a.vars);
int[] pb = posArray(vars, b.vars);
double[][] val = new double[1 << vars.length][N + 1];
for (int m = 0; m < val.length; m++) {
double[] x = a.val[project(m, pa)];
double[] y = b.val[project(m, pb)];
double[] out = val[m];
for (int i = 0; i <= N; i++) {
if (x[i] == 0.0) continue;
for (int j = 0; i + j <= N; j++)
if (y[j] != 0.0) out[i + j] += x[i] * y[j];
}
}
return new Factor(vars, val);
}
/**
* 求和消去变量：x=0 时多项式不变；x=1 时雷数加一 → 系数整体右移一位。
* 这一步正是"全局雷数计数"的来源，无需额外的计数变量。
*/
static Factor sumOut(Factor f, int var) {
int k = f.posOf(var);
int[] vars = new int[f.vars.length - 1];
for (int i = 0, j = 0; i < f.vars.length; i++)
if (i != k) vars[j++] = f.vars[i];
double[][] val = new double[1 << vars.length][N + 1];
for (int m = 0; m < val.length; m++) {
double[] e0 = f.val[insertBit(m, k, 0)];
double[] e1 = f.val[insertBit(m, k, 1)];
double[] out = val[m];
for (int c = 0; c <= N; c++) {
double v = e0[c];
if (c >= 1) v += e1[c - 1];
out[c] = v;
}
}
return new Factor(vars, val);
}
/* ============ min-fill 消元序 ============ */
static int[] minFillOrder(List<Factor> factors, Set<Integer> vars, int keep) {
Map<Integer, Set<Integer>> adj = new HashMap<>();
for (int v : vars) adj.put(v, new HashSet<>());
for (Factor f : factors)
for (int i = 0; i < f.vars.length; i++)
for (int j = i + 1; j < f.vars.length; j++)
if (vars.contains(f.vars[i]) && vars.contains(f.vars[j])) {
adj.get(f.vars[i]).add(f.vars[j]);
adj.get(f.vars[j]).add(f.vars[i]);
}
Set<Integer> alive = new HashSet<>(vars);
alive.remove(keep);
List<Integer> order = new ArrayList<>();
while (!alive.isEmpty()) {
int best = -1, bestFill = Integer.MAX_VALUE;
for (int v : alive) {
List<Integer> nb = live(adj, v, alive);
int fill = 0;
for (int i = 0; i < nb.size(); i++)
for (int j = i + 1; j < nb.size(); j++)
if (!adj.get(nb.get(i)).contains(nb.get(j))) fill++;
if (fill < bestFill) { bestFill = fill; best = v; }
}
List<Integer> nb = live(adj, best, alive);
for (int i = 0; i < nb.size(); i++)
for (int j = i + 1; j < nb.size(); j++) {
adj.get(nb.get(i)).add(nb.get(j));
adj.get(nb.get(j)).add(nb.get(i));
}
alive.remove(best);
order.add(best);
}
int[] r = new int[order.size()];
for (int i = 0; i < r.length; i++) r[i] = order.get(i);
return r;
}
static List<Integer> live(Map<Integer, Set<Integer>> adj, int v, Set<Integer> alive) {
List<Integer> nb = new ArrayList<>();
for (int u : adj.get(v)) if (alive.contains(u)) nb.add(u);
return nb;
}
/** 按给定顺序消去除 keep 之外的所有变量，返回仅含 keep 的因子 */
static Factor eliminateAllBut(List<Factor> factors, int keep, int[] order) {
List<Factor> pool = new ArrayList<>(factors);
for (int v : order) {
if (v == keep) continue;
List<Factor> bucket = new ArrayList<>();
for (Iterator<Factor> it = pool.iterator(); it.hasNext(); ) {
Factor f = it.next();
if (f.contains(v)) { bucket.add(f); it.remove(); }
}
if (bucket.isEmpty()) continue;
Factor prod = bucket.get(0);
for (int i = 1; i < bucket.size(); i++) prod = multiply(prod, bucket.get(i));
pool.add(sumOut(prod, v)); // 消息保留下来：它的多项式承载雷数计数
}
Factor prod = null;
for (Factor f : pool)
if (f.vars.length == 0 || f.contains(keep))
prod = (prod == null) ? f : multiply(prod, f);
return prod;
}
/* ===================== 棋盘与因子构建 ===================== */
static boolean revealed(int[][] b, int r, int c) { return b[r][c] >= 0; }
static boolean inBounds(int[][] b, int r, int c) {
return r >= 0 && c >= 0 && r < b.length && c < b[0].length;
}
/** 边界 = 未揭开且至少有一个已揭示邻居 */
static boolean isFrontier(int[][] b, int r, int c) {
if (b[r][c] != UNKNOWN) return false;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++)
if ((dr != 0 || dc != 0) && inBounds(b, r + dr, c + dc)
&& revealed(b, r + dr, c + dc)) return true;
return false;
}
/** 给边界格编号；非边界返回 -1 */
static int[][] frontierIds(int[][] b) {
int[][] ids = new int[b.length][b[0].length];
for (int[] row : ids) Arrays.fill(row, -1);
int cnt = 0;
for (int r = 0; r < b.length; r++)
for (int c = 0; c < b[0].length; c++)
if (isFrontier(b, r, c)) ids[r][c] = cnt++;
N = cnt;
return ids;
}
/** 每个已揭开的数字格 → 一个线索因子 */
static List<Factor> buildFactors(int[][] b, int[][] ids) {
List<Factor> fs = new ArrayList<>();
for (int r = 0; r < b.length; r++)
for (int c = 0; c < b[0].length; c++) {
if (!revealed(b, r, c)) continue;
TreeSet<Integer> vs = new TreeSet<>();
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if (!inBounds(b, nr, nc)) continue;
if (b[nr][nc] == UNKNOWN && ids[nr][nc] >= 0) vs.add(ids[nr][nc]);
}
if (vs.isEmpty()) continue; // 线索已完全满足
int v = b[r][c];
if (v > vs.size())
throw new IllegalStateException("线索与局面矛盾: (" + r + "," + c + ") = " + v);
int[] arr = new int[vs.size()];
int p = 0;
for (int x : vs) arr[p++] = x;
fs.add(Factor.clue(arr, v));
}
return fs;
}
/* ===================== 推理入口 ===================== */
/** 返回边界格概率数组，下标为边界编号 */
static double[] frontierProbs(int[][] board, int totalMines) {
int[][] ids = frontierIds(board);
double[] probs = new double[N];
if (N == 0) return probs;
List<Factor> factors = buildFactors(board, ids);
int deep = 0; // 非边界、且不与任何数字相邻的未知格
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (board[r][c] == UNKNOWN && ids[r][c] < 0) deep++;
Set<Integer> vars = new HashSet<>();
for (int i = 0; i < N; i++) vars.add(i);
for (int target = 0; target < N; target++) {
Factor f = eliminateAllBut(factors, target, minFillOrder(factors, vars, target));
double n1 = 0.0, n0 = 0.0;
for (int c = 0; c <= N; c++) {
int k1 = totalMines - 1 - c; // target=1 时其余边界格与深格共需 totalMines-1 颗雷
if (k1 >= 0 && k1 <= deep) n1 += f.val[1][c] * comb(deep, k1);
int k0 = totalMines - c; // target=0 时深格需 totalMines-c 颗雷
if (k0 >= 0 && k0 <= deep) n0 += f.val[0][c] * comb(deep, k0);
}
double s = n1 + n0;
probs[target] = (s > 0) ? n1 / s : 0.5; // 该总量下无可行解时退化为中立
}
return probs;
}
static double comb(int n, int k) {
if (k < 0 || k > n) return 0.0;
double r = 1.0;
for (int i = 0; i < k; i++) r = r * (n - i) / (i + 1);
return Math.round(r);
}
/* ===================== 穷举自校验 ===================== */
static double[] bruteForce(int[][] board, int totalMines) {
int[][] ids = frontierIds(board);
int deep = 0;
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (board[r][c] == UNKNOWN && ids[r][c] < 0) deep++;
List<int[]> clues = new ArrayList<>(); // {mines, 变量位掩码}
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++) {
if (board[r][c] < 0) continue;
int mask = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if (inBounds(board, nr, nc) && board[nr][nc] == UNKNOWN && ids[nr][nc] >= 0)
mask |= 1 << ids[nr][nc];
}
if (mask != 0) clues.add(new int[]{board[r][c], mask});
}
double[] c1 = new double[N];
double tot = 0.0;
for (int mask = 0; mask < (1 << N); mask++) {
int cf = Integer.bitCount(mask);
if (cf > totalMines || totalMines - cf > deep) continue;
boolean ok = true;
for (int[] cl : clues)
if (Integer.bitCount(mask & cl[1]) != cl[0]) { ok = false; break; }
if (!ok) continue;
double w = comb(deep, totalMines - cf);
tot += w;
for (int i = 0; i < N; i++) if ((mask & (1 << i)) != 0) c1[i] += w;
}
double[] p = new double[N];
for (int i = 0; i < N; i++) p[i] = (tot > 0) ? c1[i] / tot : 0.5;
return p;
}
/* ===================== 演示 ===================== */
// -1 表示未揭开；数字为已揭示的雷数线索
static final int[][] DEMO = {
{-1, 2, -1, -1, -1},
{-1, -1, -1, -1, -1},
{ 1, 1, 2, -1, -1},
{ 0, 0, -1, -1, -1},
{ 0, 0, 0, -1, -1}
};
static final int DEMO_MINES = 5;
public static void main(String[] args) {
int[][] board = DEMO;
double[] p = frontierProbs(board, DEMO_MINES);
int[][] ids = frontierIds(board);
System.out.println("局面（? 为未揭开）：");
for (int[] row : board) {
StringBuilder sb = new StringBuilder();
for (int v : row) sb.append(String.format("%4s", v < 0 ? "?" : String.valueOf(v)));
System.out.println(sb);
}
System.out.printf("%n边界变量数 N=%d，全局剩余雷数 M=%d%n", N, DEMO_MINES);
System.out.println("各格有雷概率（精确边缘概率）：");
for (int r = 0; r < board.length; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < board[0].length; c++)
if (ids[r][c] >= 0) sb.append(String.format("%8.3f", p[ids[r][c]]));
else sb.append(String.format("%8s", board[r][c] < 0 ? "--" : String.valueOf(board[r][c])));
System.out.println(sb);
}
double[] bf = bruteForce(board, DEMO_MINES);
double maxDiff = 0.0;
for (int i = 0; i < N; i++) maxDiff = Math.max(maxDiff, Math.abs(bf[i] - p[i]));
System.out.printf("%n与穷举枚举的最大偏差 = %.3e%n", maxDiff);
int safest = -1;
for (int i = 0; i < N; i++) if (p[i] == 0.0) { safest = i; break; }
System.out.println(safest >= 0
? "存在 100% 安全格（边界编号 " + safest + "），可直接点击"
: "本局面无确定性安全格，应按概率升序试探");
}
}
六、运行结果
局面（? 为未揭开）：
? 2 ? ? ?
? ? ? ? ?
1 1 2 ? ?
0 0 ? ? ?
0 0 0 ? ?
边界变量数 N=10，全局剩余雷数 M=5
各格有雷概率（精确边缘概率）：
0.500 2 0.500 -- --
0.167 0.833 0.000 0.583 --
1 1 2 0.583 --
0 0 0.000 0.000 --
0 0 0 0.000 --
与穷举枚举的最大偏差 = 0.000e+00
存在 100% 安全格（边界编号 4），可直接点击
这个局面很有代表性：左下的 0 已经彻底封锁，四个格子概率精确为 0.000；而 (0,0)、(0,2) 两格并列 0.500，属于真正无信息的对称格——无论怎么算都只能靠猜。中间的 0.167 / 0.833 则是耦合约束与非边界格组合权重共同作用的结果，正是局部规则法给不出的答案。
程序末尾用同一局的暴力枚举做对照，最大偏差 0.000e+00，说明消元实现与”定义本身”完全一致。这一步自校验不该省：我最初把线索因子写成自带雷数计数的版本，在小棋盘上就出现了 0.5 的偏差，全靠对照才定位到”共享变量被重复计数”。
七、复杂度与工程权衡
设边界变量数 n、诱导宽度 w：
| 环节 | 复杂度 | 说明 |
|---|---|---|
| 单次消元 | O(n · 2^(w+1) · n) | 多项式多一维，卷积额外一层循环 |
| 全边界概率 | O(n² · 2^(w+1) · n) | 当前实现为每个目标变量各跑一次消元 |
| 暴力枚举对照 | O(2^n · n) | 只用于 n ≤ 20 左右的自校验 |
三点值得强调：
- 重复消元可以优化，但先别急。为每个目标变量各跑一遍是教学实现的清晰代价。生产代码会改成两趟消息传递（桶树 / 联结树），把 n² 降到 n，代价是维护消息表。
- 宽度才是真正的敌人。扫雷边界图常为小团块或链，w 多在 2~4，此时桶消元近似线性；坏情况是”大团块 + 长链缠绕”，正确做法是按连通分量切开，逐分量独立推理。
- 确定性传播要放在消元之前。数字 0、或数字等于未知邻居数的线索，能直接推出安全/雷格；先把这些消掉，边界规模常能砍掉一半以上，桶消元的开销随之下降。
八、小结
桶消元把”扫雷猜雷”变成了”扫雷算雷”：变量消元给出精确边缘概率，多项式权重把全局雷数约束无缝并入，min-fill 排序控制最关键的宽度。这套框架能直接复用到数织、数桥、Akari 等一整类逻辑谜题——它们本质上都是因子图上的约束推理，只是因子形状不同。
真正要记住的一条经验是：精确推理必须配自校验。因子设计上的一个小疏漏（共享变量被重复计数）不会让程序崩溃，只会让概率悄悄偏移，而只有穷举对照才能抓住它。
