貌似是微软的一个面试题：扫雷游戏，给出一个雷图，让求出每一个未知块是雷的概率。身为数学盲，概率论61分的菜鸟表示概率这东西没有任何想法，但是想了下确定某一块是雷还是非雷这点还是可以搞定的...
于是就YY了一道ACM题，输入一个合法雷图，要求标记其中一定为雷和一定不为雷的块
开始想暴力，暴力可以解决任何问题，但是太麻烦了，复杂度也高，完全搞不来
然后想网络流，网络流可以求出一个可行解，但貌似没有好的方法确定某一块（我只能想到枚举删除每个点的拆边），这完全是没有意义的
后来想到一个块只有两种状态，是雷和非雷，就想到前一段练过的2-sat了，也看到松鼠会里面介绍扫雷逻辑，把扫雷转化为一个逻辑门电路的问题，然后说这是一个SAT问题，最后说这是一个NP问题。既然每个块只有两种状态，那就是2-SAT了，2-SAT可不是NP啊，或许我理解的有问题，不过貌似可以写代码了...
基本思想：
基本思想就是把一个逻辑关系用一条边来表示，从而将逻辑的传递关系转变成了图论中的连通问题，比如说：
如果事件A发生，则事件B肯定发生，就建边 A-&B
如果事件B发生，则事件C不能发生，就建边 B-&~C
这样建出的图就是 A-&B-&~C，那么我们就可以得到 A-&~C，即如果A发生，那么C不能发生
我们将一个事件的两种状态拆为两个点，然后按上面的逻辑关系建图，然后我们判断两个状态之间的连通性：
A-&~A，如果A发生了，那么A不能发生，说起来有点怪，换句话说就是A不能发生，如果A发生那么就会出现矛盾的逻辑关系
同样，如果~A-&A，则A肯定发生，如果两条边都有，那么有肯定这些逻辑关系中有矛盾，如果都没有边，那么就不能确定，两种情况都可以
从上面的分析来看，把一个未知块拆为两个点，一个表示该点为雷(x)，另一个表示非雷(~x)
然后枚举每个数字建边
0：0周围不会有雷的(x-&~x)，起始时不会出现0周围有块的情况，但之后会出现，下面会提到
1～8：如果数字n周围有k(k&=n)个未知块，那么只有两种情况可以判断：k=n时，全是雷，对每一个雷块建边 (~x-&x)；k=n+1，如果有一块不是雷，那么其他块全是雷，对每一个x块，令其他块为x'，则(~x-&x')
然后还可以想到数字1还有一些情况：对于1周围有大于1块时，如果某一块是雷，那么其他都不是雷 (x-&~x')
这样建好图，我们发现，我们人能判断的逻辑关系已经基本（后面还会说到一种情况）都加到图中了，然后重点到了：
对于一个点的两种状态，我们通过判断他们的连通情况来判断：
如果存在 x-&~x且~x-&x，也就是说存在矛盾，该情况不可能，我们保证是合法情况，不去考虑了
存在x-&~x但不存在~x-&x，说明某块不可能是雷
存在~x-&x但不存在x-&~x，说明某块肯定是雷
两个点不连通，好吧，这个块还不能确定
这样，就像人判扫雷一样，扫了一遍，但是我们发现，这样一次做过后并不能判断出全部的雷块和非雷块，对一些判断比较复杂的块还是可以确定他是雷非雷的，那么我们就多做几次好了，我们把前一次判断出来的雷和非雷加入新一轮的判断中，是雷的话就把周围数字减1，块数减1，非雷的话块数减1（这时候就会有0了），然后继续做，直到没有新的状态被确定为止，扫雷完成！！
(O不是雷，X是雷，#不确定)
下面代码：
1 #include&cstdio&
2 #include&cstring&
3 #include&cctype&
4 using namespace
6 char maze[15][15];
7 int id[15][15],
8 int dir[8][2]={{-1,-1},{-1,0},{0,-1},{-1,1},{1,-1},{0,1},{1,0},{1,1}};
9 bool gra[100][100]; 10 int lx, 11
12 void floyd(int n){ 13
for(int k=0;k&n;k++){ 14
for(int i=0;i&n;i++){ 15
for(int j=0;j&n;j++){ 16
gra[i][j]|=gra[i][k]&gra[k][j]; 17
22 void build(){ 23
memset(gra,false,sizeof(gra)); 24
for(int i=0;i&(tid&&1);i++) gra[i][i]=true; 25
for(int ii=0;ii&ii++){ 26
for(int jj=0;jj&jj++){ 27
if(isdigit(maze[ii][jj])){ 28
int cnt=0,type=maze[ii][jj]-'0'; 29
int block[10]; 30
for(int kk=0;kk&8;kk++){ 31
int tx=ii+dir[kk][0]; 32
int ty=jj+dir[kk][1]; 33
if(tx&0||ty&0||tx&=lx||ty&=ly) continue; 34
if(maze[tx][ty]=='X') type--; 35
if(maze[tx][ty]!='#') continue; 36
block[cnt++]=id[tx][ty]; 37
if(type){ 39
if(cnt==type){ 40
for(int i=0;i&i++){ 41
gra[block[i]&&1|1][block[i]&&1]=true; 42
}else if(cnt-1==type){ 44
for(int i=0;i&i++){ 45
for(int j=0;j&j++){ 46
if(i==j) continue; 47
gra[block[i]&&1|1][block[j]&&1]=true; 48
for(int i=0;i&i++){ 53
gra[block[i]&&1][block[0]&&1|1]=true; 54
if(type==1){ 57
for(int i=0;i&i++){ 58
for(int j=0;j&j++){ 59
if(i==j) continue; 60
gra[block[i]&&1][block[j]&&1|1]=true; 61
70 int main(){ 71
freopen("ms.in","r",stdin); 72 //
freopen("ms.out","w",stdout); 73
int t,cas=0; 75
scanf("%d",&t); 76
while(t--){ 77
scanf("%d%d",&lx,&ly); 79
for(int i=0;i&i++){ 80
scanf("%s",maze[i]); 81
for(int j=0;j&j++){ 82
if(maze[i][j]=='#'){ 83
id[i][j]=tid++; 84
bool flag=true; 88
while(flag){ 89
build(); 91
floyd(tid&&1); 92
flag=false; 94
for(int i=0;i&i++){ 95
for(int j=0;j&j++){ 96
if(maze[i][j]=='#'){ 97
bool a=gra[id[i][j]&&1][id[i][j]&&1|1]; 98
bool b=gra[id[i][j]&&1|1][id[i][j]&&1]; 99
if(a&b){100
puts("~~");101
}else if(b){102
maze[i][j]='X';flag=true;103
}else if(a){104
maze[i][j]='O';flag=true;105
printf("Case %d:\n",++cas);112
for(int i=0;i&i++){113
puts(maze[i]);114
puts("");116
我代码比较挫的，大致算起来O(n^4)，不错，确实太大了，为了偷懒用了floyd判连通，这个地方可以改成做n次dfs，也就可以将O(n^3)的减到O(n^2)，O(n^3)的总复杂度还是可以接受，另外那个while(true)循环，理论说可能做n次，不过我实在构造不来这样的数据，那个循环最多也就做两三次的样子，所以这个方法还是比较理想的～～（n为未知块个数&2，程序能处理最多50个未知块的数据，可以把数组范围适量改大）&&
扫雷时候还有另外的一种情况的判断，那就是给出雷的个数，雷的个数在扫雷后期还是很有作用的，比如下面的雷图：
221 XX2 #X2
剩1个或是0个雷，还有一些更复杂的情况，都可以通过雷的个数来判断某些块中是否存在雷，这样的问题不能用上面的方法来搞定，但是用概率就简单多了，又转化成了求概率的问题...
经过上面的一通乱搞，与数字相关的未知块都扫的差不多了，当然还有，尤其是一排2和一排1的情况，不过在上面的基础上求概率应该就简单多了...
#3223# ######
#2112#######
本文地址：&
阅读(...) 评论()经典证明：扫雷是NP完全问题&--The&Aha&Moment
此文转载自：
博客的名字很有意思： & & Matrix67: The
Aha Moments
博文和名字算是呼应了，问题和分析的确会让人“啊哈”一下，妙哉的感觉！
推荐大家：
经典证明：扫雷是NP完全问题
&&&&曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。
&&&&首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的。
&&&<img src="/blog7style/images/common/sg_trans.gif" real_src ="/blogimage/.gif" ALT="" STYLE="height: max-width: 100%;"
TITLE="经典证明：扫雷是NP完全问题&--The&Aha&Moment" />
&&&&上图就是一条带有Boolean值的线路。注意到x和x’中有且仅有一个有雷。如果（沿线路方向）前一个格子有雷，我们就说这条线路状态为True；反之如果后一个格子有雷，那么这条线路所传递的Boolean值就是False。每条线路的起始端都如下图左所示，其中符号*表示该格里必然有雷，x和x’中同样是有且仅有一个有雷，但到底是哪一个里面有雷谁也说不清楚。线路是可以拐弯的，如下图右所示，这可以保证转角后Boolean值相同。
&&&<img src="/blog7style/images/common/sg_trans.gif" real_src ="/blogimage/.gif" ALT="" STYLE="height: max-width: 100%;"
TITLE="经典证明：扫雷是NP完全问题&--The&Aha&Moment" />
&&&&我们需要构造一些特殊的扫雷布局来解释NOT门、AND门和OR门。构造NOT门最为简单，下图就是一个NOT门，注意经过了中间的NOT门后，x和x’的位置互换，True变成了False，False也将变成True。
&&&<img src="/blog7style/images/common/sg_trans.gif" real_src ="/blogimage/.gif" ALT="" STYLE="height: max-width: 100%;"
TITLE="经典证明：扫雷是NP完全问题&--The&Aha&Moment" />
&&&&AND门和OR门的构造就比较复杂了。下面是AND门的构造，U和V是输入的两条线路，T是输出的线路。为了说明这确实是一个AND门，我们将说明：在下面的构造中，如果线路T是True（即最右边那个格子t有雷）的话，那么格子u和v必须都有雷才行。如果最右边的格子t有雷，我们可以很快推断出，图中所有其它的t格都是有雷的，所有t’都是无雷的。观察a3正上方的那个”3&P，我们立即看出a2,a3都必须有雷，于是继续推得a1无雷，s有雷。类似地，我们可以知道r也是有雷的。在中间一行的*4t处，4的上下左右都已经有雷了，那么u’和v’必然无雷，于是继续往左推得u和v都有雷。
&&&<img src="/blog7style/images/common/sg_trans.gif" real_src ="/blogimage/.gif" ALT="" STYLE="height: max-width: 100%;"
TITLE="经典证明：扫雷是NP完全问题&--The&Aha&Moment" />
&&&&OR门的构造比较类似，如下图。如果r无雷的话，可知a2,a3有雷，a1无雷，s’有雷，进而s无雷。观察”6&P可知u’和v’都有雷，于是u和v均无雷。
&&&<img src="/blog7style/images/common/sg_trans.gif" real_src ="/blogimage/.gif" ALT="" STYLE="height: max-width: 100%;"
TITLE="经典证明：扫雷是NP完全问题&--The&Aha&Moment" />
&&&&不断套用这几个逻辑门的构造图来连接电路，直到输出线路只剩下唯一的一条。把最后的输出线路从x或者x’处截断（相当于把最终输出的Boolean值定下来）后，整个布局就成了一个“扫雷版SAT问题”了。
&&&&最后还有一个容易忽略的问题：要是线路交叉了该咋办？下图的构造可以保证线路交叉后仍不改变原线路所带的Boolean值。至此，我们已经可以把任一逻辑电路布局到扫雷棋盘上，解决这个扫雷问题就相当于要解一个逻辑电路问题，因此扫雷问题至少和逻辑电路问题一样难。
&&&<img src="/blog7style/images/common/sg_trans.gif" real_src ="/blogimage/.gif" ALT="" STYLE="height: max-width: 100%;"
TITLE="经典证明：扫雷是NP完全问题&--The&Aha&Moment" />
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。每日一博 | WinformGDI+入门级实例——扫雷游戏 - 推酷
每日一博 | WinformGDI+入门级实例——扫雷游戏
整体思路：
扫雷的游戏界面让我从一开始就想到了二维数组，事实上用二维数组来定义游戏数据确实是最符合人类思维的方式。(Square类会在后面解释)
//游戏数据
private readonly Square[,] _gameD
有了这个开头，接下来就是填充二维数组的数据了，对于数据，我最初的想法是用int或枚举，当然，这是可行的，但涉及一个问题就是高耦合，所有操作将都在高层执行，难以维护。
于是我们用一个Square类表示一个小方块区。
/// &summary&
/// 表示游戏中一个方块区
/// &/summary&
public sealed class Square
以枚举表示方块区的状态：
/// &summary&
/// 方块区状态
/// &/summary&
public enum SquareStatus
/// &summary&
/// &/summary&
/// &summary&
/// 已打开
/// &/summary&
/// &summary&
/// 已标记
/// &/summary&
/// &summary&
/// 已质疑
/// &/summary&
/// &summary&
/// 游戏结束
/// &/summary&
/// &summary&
/// 标记失误(仅在游戏结束时用于绘制)
/// &/summary&
MarkMissed
用Game类来表示一局游戏，其中包含游戏数据、游戏等级、雷区数、布雷方法等。
/// &summary&
/// 游戏对象
/// &/summary&
public sealed class Game
难点攻破：
游戏不大，涉及的难点也就不多，但对于刚接触GDI+的读者，一些地方还是比较麻烦的。
逻辑难点1：布雷
扫雷游戏有一个附加规则，就是第一次单击不论如何都不会踩到雷区，由于这个规则的存在，我们不能将布雷操作做在第一次单击之前。所以我们在游戏开局时假设所有方块区都没有雷。
/// &summary&
/// 开始游戏
/// &/summary&
public void Start()
//假设所有方块区均非雷区
for (int i = 0; i & _gameData.GetLength(0); i++)
for (int j = 0; j & _gameData.GetLength(1); j++)
_gameData[i, j] = new Square(new Point(i, j), false, 0);
随后，在开局后第一次单击时布雷。
/// &summary&
/// &/summary&
/// ¶m name=&startPt&&首次单击点&/param&
private void Mine(Point startPt)
Size area = new Size(_gameData.GetLength(0), _gameData.GetLength(1));
List&Point& excluded = new List&Point& { startPt };
//随机创建雷区
for (int i = 0; i & _minesC i++)
Point pt = GetRandomPoint(area, excluded);
_gameData[pt.X, pt.Y] = new Square(pt, true, 0);
excluded.Add(pt);
//创建非雷区
for (int i = 0; i & _gameData.GetLength(0); i++)
for (int j = 0; j & _gameData.GetLength(1); j++)
if (!_gameData[i, j].Mined)//非雷区
int minesAround = EnumSquaresAround(new Point(i, j)).Cast&Square&().Count(square =& square.Mined);//周围雷数
_gameData[i, j] = new Square(new Point(i, j), false, minesAround);
_gameStarted =
先创建雷区，再创建非雷区，以便我们在创建非雷区时可以计算出非雷区周围的雷数，枚举周围方块的方法我们用yield创建一个枚举器。
/// &summary&
/// 枚举周围所有方块区
/// &/summary&
/// ¶m name=&squarePt&&原方块区&/param&
/// &returns&枚举数&/returns&
private IEnumerable EnumSquaresAround(Point squarePt)
int i = squarePt.X, j = squarePt.Y;
//周围所有方块区
for (int x = i - 1; x &= i + 1; ++x)//横向
if (x & 0 || x &= _gameData.GetLength(0))//越界
for (int y = j - 1; y &= j + 1; ++y)//纵向
if (y & 0 || y &= _gameData.GetLength(1))//越界
if (x == squarePt.X && y == squarePt.Y)//排除自身
yield return _gameData[x, y];
逻辑难点2：当单击区周围无雷区(空白)时，自动批量打开周围所有非雷区
//如果是空白区，则递归相邻的所有空白区
if (_gameData[logicalPt.X, logicalPt.Y].MinesAround == 0)
AutoOpenAround(logicalPt);
/// &summary&
/// 自动打开周围非雷区方块(递归)
/// &/summary&
/// ¶m name=&squarePt&&原方块逻辑坐标&/param&
private void AutoOpenAround(Point squarePt)
//遍历周围方块
foreach (Square square in EnumSquaresAround(squarePt))
if (square.Mined || square.Status == Square.SquareStatus.Marked || square.Status == Square.SquareStatus.Opened)
square.LeftClick();//打开
//周围无雷区
if (square.MinesAround == 0)
AutoOpenAround(square.Location);//递归打开
绘图难点1：双缓冲以克服闪烁
从二维数组的结构来看，我们需要遍历整个二维数组，然后把每个Square绘制到winform上，但这会造成强烈的闪烁效果。因为是实时绘图，绘制的每一步都会实时显示在窗口上，所以我们看到的效果就是一个方块区一个方块区的出现在窗口上。
为了克服这种不友好的闪烁，双缓冲出现了，思路就是创建一个缓冲区(通常是一个内存中的位图)，先将所有方块区绘制到这张位图上，绘制完成后，将位图贴到窗体上，最终效果将不再出现闪烁的情况。
//窗口图面
private readonly Graphics _wndG
private readonly Bitmap _
//缓冲区图面
private readonly Graphics _bufferG
/// &summary&
/// 绘制一帧
/// &/summary&
public void Draw()
for (int i = 0; i & _gameData.GetLength(0); i++)
for (int j = 0; j & _gameData.GetLength(1); j++)
_gameData[i, j].Draw(_bufferGraphics);
_wndGraphics.DrawImage(_buffer, new Point(_gameFieldOffset.Width, _gameFieldOffset.Height));
至此，所有难点基本攻破，完整代码大家参考附件，代码基于Windows XP版扫雷做的模仿，笔者能力有限，不足之处请大家多多指点。
http://git.oschina.net/muxiangovo/Mine
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致人人网 - 抱歉
哦，抱歉，好像看不到了
现在你可以:
看看其它好友写了什么
北京千橡网景科技发展有限公司：
文网文[号··京公网安备号·甲测资字
文化部监督电子邮箱：wlwh@··
文明办网文明上网举报电话： 举报邮箱：&&&&&&&&&&&&您现在的位置： &
高玩分析：扫雷第一步先戳哪里最高效
12:08:54 发表 | 来源：网络
扫雷作为策略游戏，需要游戏者精确的判断。在面对一个超大雷阵时，如何才能做到&迅风扫落叶&？这当然需要一定的技巧，而技巧的高下之分，其实从第一步就已经开始。
Windows系统保证了扫雷的第一步无论点击哪个方块都是安全的。一名普通玩家一上来大概会很随意地点击一个方块，反正不晓得哪个是雷又肯定是安全的，点哪不一样。但对高手来说，却是每一步都要运筹帷幄。
在扫雷游戏中，如果你点击的方块附近都没有地雷，点击的后果就是一片没有雷的区域瞬间展开了，然后我们就可以根据区域边缘的数字慢慢排雷。
于是问题来了：第一步点击什么位置碰到安全区域的几率更大？是角、边还是中间？这当然需要算一算。
扫雷也是有学问的
金角银边草肚皮
首先不难看出，点击某个方块出现一片安全区域的条件是这个方块的周边没有地雷。假设我们第一次点击的方块处在盘面中间的位置，那么就需要它周围的8个方块都没有雷；如果方块在盘面的4条边上，则是5个方块；在角上是3个方块。
金角银边草肚皮
假如我们第一次点击的方块在盘面中间，那么出现安全区域的概率就等于它周围8个方块都没有雷的概率(暂且不论这个安全区 域可以有多大)。如下图所示，令N表示盘面上格子的总数，M表示地雷的个数，前面说过因为第一次点击的一定不是雷，所以这时候场上还剩N-1个格子和M个 地雷，于是图中右下角那个格子不是雷的概率就是(N-M-1)/(N-1)。
类似地，当前场上还剩N-2个格子和M个雷，所以下一个格子依然不是雷的概率是(N-M-2)/(N-2)。
依此类推，最后可以发现，第一次点击的格子，其周围没有雷的概率是：
对于边和角的情况，推导的过程完全类似，只是上述乘积的项数不一样&&边上只有5项，角上只有3项。
根据游戏的设置，将N和M的取值代入这个表达式中，最终可以得到三种难度下三种策略各自出现安全区的可能性大小：
统计学规律
所以得出的结论是，&从角上开局&！
安全区有大有小
当然，看到这里你可能有个疑问，虽然说第一步点击角出现安全区的概率最大，但安全区域的面积也有大有小。一个直观的想法是，虽然角上出现安全区域的可能性最大，但其能扩展出的面积也最受限制，而在中间的位置，虽然安全区出现的可能性最小，但是一旦出现，这个区域可以向四周发散，能扩展出的面积也随之增大。这两个因素相互制约，究竟谁能最终胜出？
我们转而考虑另一个指标，也就是某一个方块被点击后出现的安全区域的平均面积。这个指标在概率论和统计学中称为期望值。但因为安全区域面积的期望大小很难从理论上推导出来，所以在这里我们利用了蒙特卡罗模拟的办法来对它进行计算。其主要流程就是在电脑中模拟很多次扫雷的过程(比如10万次)，然后把每一次的结果记录下来，最后做一次平均。
下图是初级模式下游戏开始第一步，点击每个格子出现安全区域的期望面积，可以看出，颜色越浅的地方安全区域面积倾向于越大，在图中即为四个角的位置，平均下来一次可以击出约16个格子。最&差&的地方则是从外向里第二圈的四个顶点，仅为10个格子左右。这其实也符合记录。初级扫雷的世界纪录是1秒，世界上很多人达到了这一点。在1秒的时间里完成初级扫雷其实属于碰运气，最可能的方法就是直接点击4个角的方块。
类似地，中级和高级的图如下所示：
中级和高级
其中颜色最浅的地方都指向了四条边的中心。
所以，如果考虑的是连击区域的大小，那么在初级模式下还是应该优先选择四个角的位置；而对于中级和高级模式，则是边的中心其大小的期望值最大。
模拟结果存在不足
然而上面用蒙特卡罗方法得出的结果却并不就是我们想要的答案。计算机模拟的只是第一步点击哪里出现安全区域的期望面积最大，但实际上，第一次点击出现的安全区域面积越大，下一次点击未知区域出现安全区域的概率也就越小，区域面积也会越小。如果只是贪图第一步捡一个大便宜，而让之后的操作寸步难行，那未免得不偿失。
另一方面，并非每一个扫雷局都是有解的，有时候根据现有的局面，并不能够判断最后剩下的几个方块哪个是雷哪个不是，例如下图这种情况，剩下两个方块各自有雷的概率都是50%。
这个你怎么点？
出现这种情况，除了因为地雷布局的原因，还和游戏者的操作有关。试想辛辛苦苦大半天，最后却只能&谋事在人成事在天&，未免太亏。而如果第一步就点击角落，自然就降低这种局面出现的概率。
对于扫雷游戏来说，首要目的是要排出全部地雷，其次是尽量缩短游戏时间。根据前面的推算，我们知道，首先点击角无疑会让这个游戏变得更为简单和容易，并且也不会为之后的操作带来什么麻烦，作为一名技术流高手，第一步首先点击角落的方块，无疑是最保险和高效的。
结论很简单
延伸阅读：想扫雷高手？先练好逻辑吧
扫雷作为策略游戏，需要游戏者精确的判断。现在扫雷高级的官方最快纪录是33.95秒，中级则是由一个波兰玩家保持的8.5秒，而初级纪录是1秒，世界上很多人达到了这一点。在1秒的时间里完成初级扫雷，据测算概率在0.00058%至0.00119%之间(属于运气题)，最可能的方法是直接点击四个角的方块。下边我们就要将雷与雷之间的规律给你揪出来，并且深入思考其中的内涵。让你以后面对扫雷时，缩短与记录的差距，战无不胜！
从简单雷区入手
下图是一个初级的雷区，并且标注了两颗雷的位置，你能将剩下的地雷扫描出来吗？
这个很简单吧
经过逐一排查，可以很轻松的确定雷区中的6颗地雷所在位置：
再来看一个简单的&雷区&：
这个看似不难，实际上&&
通过逐步扫描每一个方块会发现：首先最左边的和最右边的两个格子都一定是地雷，从左数第二个空格子和从右数第二个空格子 也都是地雷，由于数字1的关系，从左数第3个格子和从右数第3个格子都不是地雷，翻开一定是数字1&&这样一直下去，最后你会发现最中间的两个空格子，不 管有没有地雷，都和周围格子上的数字不符。也就是说这样的雷区有bug，是无解的。
雷区中的逻辑门
怎么判断一个雷区是否有bug？又怎么判断雷区中地雷的具体位置呢？难道一定要从头到尾将雷区扫描一遍吗？
其实这些雷区里其实藏着一个规律。我们用数学方法来分析了上例的雷区：
在之前提到的这两个雷区里，把还没有翻开的格子交叉标记上字母x和x&。可以看到：当x的格子有雷时，x&格子一定没有 地雷，反之亦然。如果将最左边的空格子作为输入，把最右边的格子作为输出，输入结果和输出结果一定是一样或者相反的。如果是相反的，这相当于一个 NOT(&非&)门电子元件。如果是一样的，就有趣了，这样的一片雷区就具备了电路导线的性质！
就是这样的
在这里，雷区被看成了一个数字逻辑电路。执行这些&或&、&与&、&非&等逻辑运算的电路则被称为&&逻辑门。任何复杂的逻辑电路都可由这些逻辑门组成。
逻辑门是集成电路上的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种型号的高低电平在通过它们 后产生信号。而高低电平可以分别代表逻辑上的真假或二进制中的0和1，从而实现逻辑运算。具体到扫雷游戏里，也就是说，逻辑门可以用于判断一系列格子中的 地雷的具体位置，而且它如同电路传导一样，精确而迅速。
常见的(也是扫雷中用到的)逻辑门包括&与&门、&或&门、&非&门等。将它们组合使用就可以实现更复杂的运算&&完成复杂情形下的扫雷，这种方法比按照规则缓慢推进的扫雷方法要节省很多时间。
复杂雷区中的精确判断
在简单的雷区中小试牛刀后，带着发现的规律，让我们进行一次实战演习。下图是高级扫雷游戏中的一个典型的雷区：
你能在不翻开格子的情况下，直接指出黄格子中有无地雷吗？ 如果将雷区随意改变一点&&左上角的一个格子下移一位，结果又如何呢？
你可能需要考量全局，从某个点开始逐步推理，将雷区全部扫描一遍，才能判断，而当雷区任意改变一点时，你都要重新来过，才能再次解答。这无疑是一种巨大成本负担。
实际上我们可以很快速地给出答案：第一个雷区的黄格子中无雷，而第二个雷区的黄格子中一定有雷。
这是怎么做到的？其实将上述的逻辑门引入到这个复杂的雷区中，一切都会变得简单而清晰起来。
看成电路就好分析了
雷区内靠近边界、可以直接确定是地雷的位置都插上了标示旗，剩下的位置标上了不同的字母。把一个有地雷格子看作1，没有地雷的看作0。最左面的格子(u、v)作为输入，最右面的格子(t)作为输出。按照扫雷游戏的规则，经过一步步推算，它们之间的关系就是：
( u , v , t ) = ( 1 , 1 , 1 ) 或 ( 1 , 0 , 0 ) 或 ( 0 , 1 , 0 ) 或 ( 0 , 0 , 0 )
显然，这个雷区被归纳成了一个AND门，它不仅轻松化解了这个扫雷难题，而且把雷区的规律揭示出来了。如此一来，当你掌握扫雷中这些逻辑门规律并加以练习后，就能够达到精确、快速的&机械化&扫雷水准。到那时，一个新纪录或许就会诞生了。
数学家的扫雷研究
将扫雷问题抽象化从而缩短游戏时间的人，也不仅仅是扫雷发烧玩家。一些数学家也十分关注这个游戏背后的数学意义。
英国一位数学家用扫雷游戏中的逻辑规律构建了一系列电子元件，用电子电路模拟雷区。他试图将一个的给定的雷区图案交由计 算机来判断是否可解。如果随着格子数量的增加，电脑的计算量增长不是很快，就是P问题，如果计算量增加的很快，就是NP问题。计算机判断雷区是否可解，需 要这类问题属于P问题才可以。
对于几种基本的电路元件(AND、OR、NOT)，如果将很多个这样的元件组合起来，相互连接，就会产生很多个输入、输出口。判断最后哪些输出结果可以产生，哪些不可以产生的这类问题，被称为SAT问题，它属于一个经典的NP完全问题。
而英国数学家的这个问题在一些时候等同于一个复杂电子电路的SAT问题，也就是NP完全问题。由此看来，面对一个上千上万个格子的巨型雷区，不要说去完成所有扫雷任务，就仅仅判断它是不是可解的，都可能会是计算机也承受不了的的大难题。
7K新浪官方微博
7K腾讯官方微博
已有10000人
已有10000人
查看相关新闻
AV女优代言页游 宅男们你们怎么看？
热门专区推荐
