扫雷中的数学原理
目录
一，方程组
二，不等式组
三，无计算推理
1，无计算推理的原理
2，扫雷代码V3
3，实战效果
四，总结
一，方程组
假设3个格子对应的未知数分别是x1 x2 x3，表示格子中的雷的数量
则根据x2右边的2可得，x1+x2+x3=2
根据x3右边的3可得，x2+x3=1
所以，求解方程组可得，x1=1
验证答案：
二，不等式组
扫雷的推理过程中，无论有几个未知数，每个未知数x都自带一个不等式0<=x<=1
这里我们列出不等式组
0<=x1<=1
0<=x2<=1
0<=x3<=1
0<=x4<=1
x1+x2+x3=2
x2+x3+x4=1
求解这个不等式组：
首先我们得到x2+x3<=1
所以我们就可以得到x1=1，x2+x3=1，x4=0
验证答案：
三，无计算推理
1，无计算推理的原理
实际扫雷时，我们会大量运用这样的一条策略：双击某个数字，如果只剩1个格子未标记，则标记它。
这个方法不需要做任何的计算，但是却有奇效。
2，扫雷代码V3
为了直观的感受这个单一策略的上限有多高，我基于串行扫雷里面的扫雷代码V1做微调，加入2条自动规则：
（1）如果一个格子周围只有一个格子未标记，且双击无反应，则自动标记
（2）如果一个格子周围标记的数量达标，则自动双击。
我们看下在自动规则下，串行的去扫雷还需要多少步骤。
代码：
#include <iostream>
#include <string>
#include <vector>
#include <time.h>
#include <functional>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <functional>
#include <string.h>
#include <math.h>
#include <fstream>
#include <streambuf>
#include <stdio.h>
#include <mutex>
#include <unordered_map>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
#include <math.h>
#include <functional>
#include <limits>
#include <climits>
#include <stdint.h>
#include <windows.h>using namespace std;#define LOCALint ROW = 16;
int COL = 30;
int BOMB = 99;enum Nod {EmptyGrid,BombGrid
};
enum Status {Unknow,Open,Flag
};vector<vector<int>>v;//雷分布
vector<vector<int>>vsum;//雷计数
vector<vector<int>>vs;//实时界面
bool isWin;
int hseed;//棋谱中的种子
vector<int>hr, hc, ho;//棋谱中的行、列、操作数
int autoNum;void init(int seed)
{srand(seed);v.resize(ROW);vsum.resize(ROW);vs.resize(ROW);for (auto& vi : v) {vi.resize(COL);for (auto& x : vi)x = EmptyGrid;}for (auto& vi : vsum) {vi.resize(COL);for (auto& x : vi)x = 0;}for (auto& vi : vs) {vi.resize(COL);for (auto& x : vi)x = Unknow;}int b = BOMB;while (b) {int r = rand() % ROW;int c = rand() % COL;if (v[r][c] == BombGrid)continue;v[r][c] = BombGrid;b--;for (int i = max(0, r - 1); i <= min(r + 1, ROW - 1); i++) {for (int j = max(0, c - 1); j <= min(c + 1, COL - 1); j++) {vsum[i][j]++;}}}isWin = false;autoNum = 0;
}//鼠标左键单击,是否阵亡
bool clickLeft(int r, int c)
{if (v[r][c] == BombGrid) {return true;}if (vs[r][c] == Open)return false;vs[r][c] = Open;if (vsum[r][c])return false;for (int i = max(0, r - 1); i <= min(r + 1, ROW - 1); i++) {for (int j = max(0, c - 1); j <= min(c + 1, COL - 1); j++) {clickLeft(i, j);}}return false;
}
//鼠标右键单击,是否阵亡
bool clickRight(int r, int c)
{vs[r][c] = Flag;return v[r][c] != BombGrid;
}
//鼠标左键双击,是否阵亡
bool clickDouble(int r, int c)
{for (int i = max(0, r - 1); i <= min(r + 1, ROW - 1); i++) {for (int j = max(0, c - 1); j <= min(c + 1, COL - 1); j++) {if (vs[i][j] != Flag && clickLeft(i, j))return true;}}return false;
}
//自动点击，是否刷新局面
bool clickAuto()
{for (int r = 0; r < ROW; r++) {for (int c = 0; c < COL; c++) {if (vs[r][c] != Open)continue;int flagNum = 0;int unknownNum = 0;for (int i = max(0, r - 1); i <= min(r + 1, ROW - 1); i++) {for (int j = max(0, c - 1); j <= min(c + 1, COL - 1); j++) {if (vs[i][j] == Unknow)unknownNum++;if (vs[i][j] == Flag)flagNum++;}}//如果一个格子周围只有一个格子未标记，且双击无反应，则自动标记if (unknownNum == 1 && flagNum < vsum[r][c]) {for (int i = max(0, r - 1); i <= min(r + 1, ROW - 1); i++) {for (int j = max(0, c - 1); j <= min(c + 1, COL - 1); j++) {if (vs[i][j] == Unknow)clickRight(i, j);}}return true;}//如果一个格子周围标记的数量达标，则自动双击if (flagNum == vsum[r][c] && unknownNum > 0) {clickDouble(r, c);return true;}}}return false;
}//1左键单击，2右键单击，3左键双击，4显示棋谱,返回是否结束
bool opt(int r, int c, int optNum)
{if (optNum >= 1 && optNum <= 3) {hr.push_back(r);hc.push_back(c);ho.push_back(optNum);}if (optNum == 1 && clickLeft(r, c))return true;if (optNum == 2 && clickRight(r, c))return true;if (optNum == 3 && clickDouble(r, c))return true;if (optNum == 4) {cout << hseed << endl;for (int i = 0; i < hr.size(); i++) {cout << hr[i] << " " << hc[i] << " " << ho[i] << " ";if (i % 5 == 4)cout << endl;}Sleep(5000);return false;}while (clickAuto()) {autoNum++;cout << "autoNum=" << autoNum << endl;}for (int i = 0; i < ROW; i++) {for (int j = 0; j < COL; j++) {if (vs[i][j] == Unknow && v[i][j] == EmptyGrid) {return false;}}}return isWin = true;
}void show()
{system("cls");cout << " 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 ";cout << "22 24 26 28" << endl;int flagNum = 0;for (int i = 0; i < ROW; i++) {cout << i << " ";if (i < 10)cout << " ";for (int j = 0; j < COL; j++) {if (vs[i][j] == Unknow)cout << "■";else if (vs[i][j] == Open) {if (vsum[i][j])cout << vsum[i][j] << "_";else cout << "□";}else {cout << "●";flagNum++;}}cout << endl;}cout << "还剩" << BOMB - flagNum << "雷未标记";cout << endl;
}
void showEnd()
{cout << " 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 ";cout << "22 24 26 28" << endl;for (int i = 0; i < ROW; i++) {cout << i << " ";if (i < 10)cout << " ";for (int j = 0; j < COL; j++) {if (v[i][j] == BombGrid)cout << "●";else cout << "□";}cout << endl;}cout << endl;opt(0, 0, 4);cout << "自动执行步数=" << autoNum;
}bool run()
{show();cout << "输入行 列 操作数" << endl;cout << "1左键单击，2右键单击，3左键双击，4显示棋谱" << endl;int r, c, optNum;cin >> r >> c >> optNum;return opt(r, c, optNum);
}int main()
{cout << "输入随机数种子" << endl;cin >> hseed;init(hseed);while (!run());if (isWin)cout << "Win!!!" << endl;else cout << "Lose..." << endl;showEnd();return 0;
}3，实战效果
还是用这个纯推理开局：
666777888
15 3 1 13 0 1 15 0 1 6 0 1 6 10 1
6 20 1 6 29 1 15 15 1 8 17 1
整个推理我只花了26步：
9 13 2
12 14 2 13 23 2 10 23 1 12 26 2 13 29 2
2 28 1 3 29 1 2 27 1 2 29 1 10 27 1
10 28 1 10 29 1 9 28 1 12 2 2 13 2 2
11 2 2 11 8 2 15 5 2 10 5 1 10 4 1
11 4 1 10 1 1 10 0 1 10 2 1 11 5 1
自动执行步数=204
在串行扫雷中，基于扫雷代码V1，基于同样的开局，我的操作步数是215
由此可估算，在一局扫雷中，88%的推理都是无计算推理，方程组的计算和不等式组的计算只占12%
四，总结
扫雷其实只需要4种操作：解方程组，解不等式组，无脑双击，落单标记。
落单标记指的是，在无脑双击时，如果一个格子周围只有1个格子是未知状态，即落单了，则直接标记为雷。
刚玩扫雷的人，乐趣大概在于高频急速的脑力劳动，即一秒之内解方程组或不等式组。
熟悉双击的人，乐趣大概在于高频急速的体力劳动，即无脑双击和落单标记。