引言
扫雷是一款经典的逻辑推理游戏。玩家在揭开格子的同时，需要根据已显示的数字推断周围地雷的分布。本文将介绍一种进阶解法：利用高斯消元将扫雷的约束条件转化为线性方程组，再通过贝叶斯推理计算每个未揭示格子是地雷的概率，从而做出最优决策。
核心算法原理
1. 约束建模
扫雷中每个已揭示的数字格，其周围未揭示的格子构成一个约束：这些格子中地雷的总数等于该数字。若用变量 $x_i \in {0,1}$ 表示第 $i$ 个未揭示格子是否为地雷，则每个数字格对应一个线性方程：
$$\sum_{i \in \text{邻居}} x_i = \text{数字}$$
将所有约束收集起来，就得到一个定义在 $\mathbb{F}_2$（二元域）上的线性方程组。注意这里的等号实际上是模2等号，但由于右侧是具体的计数值而非模2值，更准确的处理是在实数域上进行高斯消元，然后结合整数约束求解。
2. 高斯消元求解
将约束写成增广矩阵形式，对实数矩阵执行高斯消元。消元后，部分变量可以被唯一确定（主元变量），而另一部分则是自由变量。对于每个自由变量的赋值组合，检查是否满足所有约束（右侧数字匹配），即可枚举出所有合法的地雷分布方案。
3. 贝叶斯概率计算
枚举出所有合法方案后，某个格子是地雷的概率为：
$$P(\text{地雷}) = \frac{\text{该格子为地雷的方案数}}{\text{总合法方案数}}$$
对于与任何数字格都不相邻的孤立区域，需要结合剩余地雷数进行全局概率修正。
Java实现
import java.util.*;
/**
* 扫雷高斯消元求解器
* 将数字约束转化为线性方程组，枚举所有合法解后计算贝叶斯概率
*/
public class MinesweeperGaussianSolver {
// 扫雷棋盘状态: -1=未揭示, 0-8=已揭示的数字, -2=已标记地雷
private int[][] board;
private int rows, cols;
private int totalMines; // 总地雷数
public MinesweeperGaussianSolver(int[][] board, int totalMines) {
this.board = board;
this.rows = board.length;
this.cols = board[0].length;
this.totalMines = totalMines;
}
/**
* 收集所有约束：每个数字格对应一个方程
* 返回形式: List<int[]> 每个int[]长度为(变量数+1)，最后一位是常数项
*/
private List<int[]> collectConstraints(List<int[]> variables) {
List<int[]> equations = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] >= 0) { // 已揭示的数字格
int num = board[r][c];
int[] eq = new int[variables.size() + 1];
int count = 0;
// 遍历8邻域
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& board[nr][nc] == -1) {
// 找到该变量在列表中的索引
for (int i = 0; i < variables.size(); i++) {
if (variables.get(i)[0] == nr && variables.get(i)[1] == nc) {
eq[i] = 1;
count++;
break;
}
}
}
}
}
// 减去已标记的地雷数
int flagged = countFlaggedNeighbors(r, c);
eq[variables.size()] = num - flagged;
if (count > 0) {
equations.add(eq);
}
}
}
}
return equations;
}
private int countFlaggedNeighbors(int r, int c) {
int count = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == -2) {
count++;
}
}
}
return count;
}
/**
* 高斯消元（实数域）
* 返回行阶梯形矩阵
*/
private double[][] gaussianEliminate(double[][] matrix, int varCount) {
int rowCount = matrix.length;
if (rowCount == 0) return matrix;
int colCount = varCount + 1;
int row = 0;
for (int col = 0; col < varCount && row < rowCount; col++) {
// 找主元
int pivot = row;
for (int i = row; i < rowCount; i++) {
if (Math.abs(matrix[i][col]) > Math.abs(matrix[pivot][col])) {
pivot = i;
}
}
if (Math.abs(matrix[pivot][col]) < 1e-9) continue;
// 交换行
double[] temp = matrix[row];
matrix[row] = matrix[pivot];
matrix[pivot] = temp;
// 归一化
double div = matrix[row][col];
for (int j = col; j < colCount; j++) {
matrix[row][j] /= div;
}
// 消去下方行
for (int i = row + 1; i < rowCount; i++) {
double factor = matrix[i][col];
if (Math.abs(factor) > 1e-9) {
for (int j = col; j < colCount; j++) {
matrix[i][j] -= factor * matrix[row][j];
}
}
}
row++;
}
return matrix;
}
/**
* 枚举所有合法解，计算每个变量的地雷概率
*/
public Map<int[], Double> solve() {
// 收集所有未揭示且未标记的变量
List<int[]> variables = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == -1) {
variables.add(new int[]{r, c});
}
}
}
if (variables.isEmpty()) return new HashMap<>();
List<int[]> constraints = collectConstraints(variables);
int varCount = variables.size();
// 转为double矩阵进行高斯消元
double[][] matrix = new double[constraints.size()][varCount + 1];
for (int i = 0; i < constraints.size(); i++) {
for (int j = 0; j <= varCount; j++) {
matrix[i][j] = constraints.get(i)[j];
}
}
double[][] reduced = gaussianEliminate(matrix, varCount);
// 识别主元列和自由变量
boolean[] isPivot = new boolean[varCount];
int[] pivotRow = new int[varCount];
Arrays.fill(pivotRow, -1);
int r = 0;
for (int c = 0; c < varCount && r < reduced.length; c++) {
if (r < reduced.length && Math.abs(reduced[r][c]) > 0.5) {
isPivot[c] = true;
pivotRow[c] = r;
r++;
}
}
// 枚举自由变量（使用DFS/回溯）
List<boolean[]> validSolutions = new ArrayList<>();
boolean[] assignment = new boolean[varCount];
enumerateSolutions(reduced, isPivot, pivotRow, varCount, 0, assignment, validSolutions);
// 计算贝叶斯概率
Map<int[], Double> probabilities = new HashMap<>();
if (validSolutions.isEmpty()) return probabilities;
for (int i = 0; i < varCount; i++) {
int mineCount = 0;
for (boolean[] sol : validSolutions) {
if (sol[i]) mineCount++;
}
double prob = (double) mineCount / validSolutions.size();
probabilities.put(variables.get(i), prob);
}
return probabilities;
}
private void enumerateSolutions(double[][] matrix, boolean[] isPivot, int[] pivotRow,
int varCount, int varIdx, boolean[] assignment,
List<boolean[]> validSolutions) {
if (varIdx == varCount) {
// 验证所有方程
if (verifySolution(matrix, assignment, varCount)) {
validSolutions.add(assignment.clone());
}
return;
}
if (isPivot[varIdx]) {
// 主元变量由对应行计算得出
int row = pivotRow[varIdx];
double value = matrix[row][varCount]; // 常数项
for (int c = varIdx + 1; c < varCount; c++) {
if (Math.abs(matrix[row][c]) > 1e-9) {
value -= matrix[row][c] * (assignment[c] ? 1 : 0);
}
}
// 主元变量必须取整数值0或1
if (Math.abs(value) < 1e-9) {
assignment[varIdx] = false;
enumerateSolutions(matrix, isPivot, pivotRow, varCount, varIdx + 1, assignment, validSolutions);
} else if (Math.abs(value - 1) < 1e-9) {
assignment[varIdx] = true;
enumerateSolutions(matrix, isPivot, pivotRow, varCount, varIdx + 1, assignment, validSolutions);
}
// 其他值表示无解分支
} else {
// 自由变量：尝试0和1
assignment[varIdx] = false;
enumerateSolutions(matrix, isPivot, pivotRow, varCount, varIdx + 1, assignment, validSolutions);
assignment[varIdx] = true;
enumerateSolutions(matrix, isPivot, pivotRow, varCount, varIdx + 1, assignment, validSolutions);
}
}
private boolean verifySolution(double[][] matrix, boolean[] assignment, int varCount) {
for (double[] row : matrix) {
double sum = 0;
for (int c = 0; c < varCount; c++) {
if (Math.abs(row[c]) > 1e-9) {
sum += row[c] * (assignment[c] ? 1 : 0);
}
}
double rhs = row[varCount];
if (Math.abs(sum - rhs) > 1e-6) return false;
}
return true;
}
public static void main(String[] args) {
// 示例: 3x3棋盘，中心为1，其余未揭示
int[][] board = {
{-1, -1, -1},
{-1, 1, -1},
{-1, -1, -1}
};
MinesweeperGaussianSolver solver = new MinesweeperGaussianSolver(board, 1);
Map<int[], Double> probs = solver.solve();
System.out.println("各格子地雷概率:");
for (Map.Entry<int[], Double> entry : probs.entrySet()) {
int[] pos = entry.getKey();
System.out.printf("(%d,%d): %.2f%%\n", pos[0], pos[1], entry.getValue() * 100);
}
}
}
复杂度分析
- 约束收集：$O(R \times C \times 8)$，即线性扫描整个棋盘。
- 高斯消元：设变量数为 $V$，约束数为 $E$，时间复杂度为 $O(E \times V^2)$。
- 解枚举：自由变量数为 $F$，最坏情况 $O(2^F \times E \times V)$。实际扫雷中，通过边界分离可将 $F$ 控制在较小范围。
- 空间复杂度：$O(E \times V)$，用于存储增广矩阵。
总结
本文将扫雷的推理问题转化为线性代数问题：通过高斯消元识别确定变量和自由变量，枚举所有合法配置后利用贝叶斯公式计算概率。该方法在高级扫雷求解器中被广泛使用，尤其在局面复杂、纯逻辑推理无法推进时，概率计算能给出最优点击策略。
