扫雷怎么玩（玩扫雷还有什么技能？）
有时，小编回想起童年和青春，眼前总是显现出一片碧蓝碧蓝的天空和嫩得出水的草地，以及以前在那上面和小伙伴们渡过的高兴的时间……
当然，你们别想错了
我说的蓝天和草地是指这个
为了防止被打小编选择提前爆头蹲防
Windows XP 确切承载很多的记忆，而且 XP 这个体系也是真的经用。Windows XP 于 2001 年 8 月 24 日正式宣布，微软在2014 年 4 月 8 日才停滞了对 Windows XP 桌面版体系的支撑服务，一直到这周二，2019 年 4 月 9 号，运行在嵌入式装备上的最后的一批 Windows XP 才失去微软的官方支撑。XP 们终于正式对我们 say goodbye 了。[1]
经典的扫雷游戏
提起 XP，不得不说操作体系自带的诸如扫雷，纸牌这一类的经典游戏真的经典，好玩又杀时光。如果可以统计全人类花在这上面的时光，估量确定是一个天文数字。。。不过尽管扫雷大家玩的时光很长，玩的次数也很多，但是我猜 99% 的玩家确定没思考过，自己玩扫雷为啥那么容易就逝世了。。。
比较一下别人家的孩子玩扫雷的速度
图片经过加速。如果你想看真正目前世界上扫雷最快的记载的话，可以去 [2] 围观
再看看自己玩扫雷的样子...
差不多就是这种程度，刚点到扫雷图标雷就已经炸了
虽然 XP 已经离我们而去，但是万幸的是 Win10 体系还能够在商店中直接搜索「minesweeper」下载官方重置了的扫雷游戏，重新领会以前的经典。
其实吧，扫雷这个游戏很多科学家也爱玩。不过一般人玩扫雷如果逝世得快，就不断重开重开重开直到碰到一个好的开局（然后又迅速地逝世掉）。科学家就不一样，如果他们玩扫雷逝世得快，他们不会重开，他们会直接证明「这个游戏通关概率为 0」。
扫雷究竟已经有这么长的历史了，剖析扫雷游戏求解概率的论文都有一大堆。作为一个熟练点击扫雷重开键的手残扫雷玩家，2021-09-28 我就来和大家体系地聊一聊扫雷的背后的故事。
扫雷秘籍
Minesweeping cheat sheet
天下武功，无坚不摧，唯快不破！
从数学上来看，扫雷就相当于一个不断给你已知条件不断求解的进程，就像一个不断增长条件的运用题。你可以通过左键点开肯定不是雷的块，右键标志你以为是雷的区域。如果你点开的这一块不是雷，那么它会告知你这块区域周围八格内有几颗雷。只要你点得足够快，雷就追不上你。
通过很简略的反证法，我们可以推出来很大一部分雷所在的地位。[3]
角落上的情况
所谓反证法，就是反过来想这个问题。如果存在这么一个向内凹的角，内部的都是空白，但是角落上是一个 1，那么这个角上必定会有一颗雷。因为如果这个处所再不是雷的话，那中间的 1 所指的雷就只能去流落了。。。同理，一条边上如果有 3 的话，那和 3 挨着的这三个必定是雷。究竟地雷兄弟们也不能挤一挤挪到一个格子上去。
位于边界时候的情况
除了这个反证法以外，在扫雷里还有很多固定的「套路」。学会这个套路，保证你扫雷功力大增，杀进小区扫雷五百强。
听起来好像很厉害的样子
在扫雷的时候其实经常会遇到一些固定的数字，比如三个持续的数字为121，此时想都不用想，就可以直接在121 两个 1 的正对方向标上雷。或者四个持续的数字1221，此时两个 2 的正对方向上也必定是雷。
121 情况下，由于左侧 1 的限制，在黄色区域内只能有一格雷，但是中间的 2 至少请求 2 格雷，所以粉色的那颗(www.isoyu.com原创版权)必定是雷。同理证明另外一侧
1221 情况下，和上面证明进程雷同，由于 1 的限制导致在黄色区域内只能有 1 格雷，所以另一个 2 正对的方格必定是雷。
「小编小编，我有个问题，那 121221 呢？依照秘籍填雷的话中间那个 1 邻近有两颗雷诶？」
似乎有问题的秘籍？
「这种情形是不可能的！左边数起三个 1 已经笼罩了上面的所有未知空格，所以地雷数至多百思特网只有 3 个。但下方显示地雷数为 1+2+2+1+2+1，在只有中间 5 个格子反复计数的情形下都到了 7，大于 3 的 2 倍。所以这种图形是不可能存在的！」
咳咳，把思路收回来，如上所述，扫雷确切是有一些套路的。每日熟读此扫雷秘籍，假以时日，扫雷技艺必将大成。
扫雷还是运气活
Lucky or not，it's a question
玩扫雷，你必需要接收，这是一款拼人品的游戏。
虽然人生已经如此地艰苦，但我还是要无情地拆穿这一点。想必你此时已经熟练控制了扫雷的套路，不过在有些时候你还是要面对猜雷这种事情，而且一招不慎，满盘皆输。。。
猜猜黄色部分的雷应当是怎么散布的？
图中黄色部分就是典范的须要猜的扫雷难题。依据角落里面的数字，我们都只能知道 12 的黄色部分里面必定只有一个雷，不过我们并不知道哪个才是雷。如果没有其它信息的话，我们辛辛劳苦大半个棋盘，最后通过这个地雷阵的概率还是只有1/8。
这种简略的断定还好，有些时候还会遇到一些藏得更加隐晦的猜的时候。
扫雷断定题
假设在我们的扫雷进程中遇到了这么一个图案，确切是一件欲哭无泪的事情。不知道怎么哭的可以先把眼泪预备好，小编马上就告知你们为啥要哭。。。从左边开端，假设第一个空位有雷，那么第二个空位没有雷，因为空位中间 1 的存在从而第三个空位有雷，依次类推。但是如果是第一个空位没有雷，而第二个空位有雷，我们也说得通。都要踩地雷了，还全部这么庞杂的难题，至于么。。。
别急，后面还有更加庞杂的。这里的 x 和之后的 * 号上是否有雷的情形一直雷同，所以这个地雷阵就像一根传递信号的导线一样。在扫雷的地图上，我们不仅仅能够做出这种简略的传递信号的导线，其实还能够实现所有的电子电路中的逻辑门的操作。[4,5]
非门电路
或门电路
这是两个「简略」的逻辑门，分离实现了将信号翻转的非门和将两路信号做或操作的或门。在另一个也很有名的沙盒游戏——《我的世界（Minecraft）》里面，玩家也可以通过游戏中的材质，红石（其实在此之前的 Windows 10 操作体系的每一年的更新代号就是用红石来命名），实现各种各样的庞杂逻辑操作，更有玩家应用红石在 Minecraft 里制作出了真正能运行的盘算机。。。
红石盘算机，具有完全的存放器，加法器等部件 [6]
算了，我已经不敢想象扫雷会变成什么样了。。。
断定有没有解都是一件很难的事情
Find solution
回到文章最开端，我们人去破解一个扫雷问题的话，很容易就会逝世掉了，那把这个问题交给盘算机来做会怎么样？然而很遗憾的是，一般情形下，盘算机目前对扫雷这个问题还是无能为力。。。
难过
稍微值得庆幸的是，在我们平时玩的比拟小的棋盘下，盘算机还可以通过搜索得到答案。
为了懂得盘算机处置问题难度的几个级别，有必要先知道一个概念——多项式时光。对于同一个算法，依据处置问题大小的不同，盘算机一般来说须要不同的时光进行盘算。用最直观的例子来说，小明要去洗衣服，他洗 1 件衣服的时光为 2 分钟，洗 5 件衣服的时光为 10 分钟，洗 10 件衣服的时光为 20 分钟，处置问题的时光随问题范围的变更为线性关系，一次多项式。现在我们假设小明还是要洗衣服，只不过现在的衣服比拟特别，他洗 1 件这种衣服的时光为 2 分钟，但洗 5 件的时光变为 32 分钟，百思特网洗 10 件的时光变为 1024 分钟，这个时候就是指数关系的，而不再是多项式了。评价一个算法，随着问题范围的增大，盘算时光怎么增加是一个十分主要的指标。
在盘算机里面，对于多项式级别的时光，我们还是以为很快的。如果把问题依照求解的难度来进行分类的话，P是指能够用多项式时光求解的问题，俗话说就是算起来很快的问题。NP是指算起来不必定快，但是任何答案我们都可以检讨起来很快的问题。NP 完整问题，是比所有 NP 问题都要难的 NP 问题。虽然人们有个美妙的想法，总认为验算起来很快的应当可以找到方法让他算起来很快，但目前还是个未知数。。。[7]
很不幸，求解一个扫雷游戏的解，正好是一个 NP 完整问题——在能够轻松验证成果是否准确的问题里面最难的那一类。这一类问标题前为止人们还没有发明多项式时光的求解算法，通常只有指数级甚至阶乘级的搜索算法来解决。
用来显示液晶数字的逻辑电路。我们可以很便利地一个一个试，但是反过来却很难，尤其是在这个逻辑电路非常宏大的时候
扫雷游戏属于一个如此艰苦的问题，其原因就出在上一章提到的，可以把扫雷游戏看做一个个逻辑门进行运算的逻辑电路。给定一个逻辑电路，在已知输出成果的情形下，能否肯定每个输入的值？这个问题被称为SAT 问题，是世界上第一个被证明其为 NP 完整的问题。[8]这种问题验证起来非常容易，你只须要把成果代入到逻辑电路中，马上能知道是否符合请求，但倒过来想要盘算符合成果的输入就极端地麻烦。
求解扫雷游戏的成果，应用那些结构的逻辑门，恰恰等价于求解 SAT 问题。[9]
扫雷还和渗透有关系
Precolation
液体，图片来自 Giphy，Michael Shillingburg
其实我们在玩扫雷游戏的时候认为很难，其实还有另外一个原因。这个原因和物理里面的渗透还有关系。
在上个世纪 60 年代，科学家们 [10] 发明在流体流过多孔的介质的时候，介质中的空泛总是会被堵塞，有时候就会影响流体流出。更为奇异的是，当这些多孔的介质的孔隙被随机堵塞的比例逐渐增大而到达某一值时，一开端一直能够流动的流体就突然被完整堵住。在孔洞被随机堵住的概率产生变更时，液体流过的比率也会产生一个突变。
这种现象被称为逾渗（precolation）。[11]
遇到这种情形，你该怎么下手
在扫雷里面，也存在相似逾渗的现象。当一盘游戏里面的地雷密度特殊低的时候，我们差不多随意点，都不会点到地雷，而是点到大片大片的空白，一下子就把问题解决了。但是当地雷密度增高以后，在增大到必定水平以后，即使我们理性地剖析，从不瞎猜，也不可能把扫雷问题做对了。
针对不同的棋盘大小，有人盘算了在不同地雷密度情形下获胜的概率。三角形对应的曲线为初级 88，正方形为 1513，菱形为高等，3016。这里的能否求解实际上不包含第一次随机点击的时候踩中雷的概率。[12]
我们把流体通过多孔介质逾渗的模型抽象出来的话，其实对应着点逾渗，也就是把全部介质想象成一个网络，流体在经过每个网格时，有概率 p 的可能通过。如果不能流过的网格在网络中连成了片，流体就不能流过了。
不严厉地来说，求解扫雷问题其实和逾渗模型很相似，我们求解的进程其实也像推土机一样，不断地应用已有的知识将已知区域向外一层一层地推动。如果游戏中某处雷的密度越大，那么越有可能涌现可解部分被雷离开的情形，地雷密度和逾渗参数起到了一样的作用。如果被分隔到无法衔接全部棋盘，那就无法持续推理了。更为严厉的证明可以参考 Elchanan Mossel 的论文。[13]
推土机，图片来自网络
随着网格的不断增大，这条胜率曲线中间部分也变得越来越峻峭，扫雷问题越来越向两个极端发展：要不就基本解不出来，要不就是很容易地就能解出来。在高等模式下，地雷的密度其实已经到了 99/480 = 0.2，能够解出来的概率已经不到 1/4，这还不算手抖了点错了，开局不好重开之类的情形，真的不算是友爱了。
结 论
Conclusion
emoji 版本扫雷 [14]
信任看到这里的人
必定已经跃跃欲试想要玩一下扫雷了
我信任你们
天下无难事，只要肯废弃
卸载也行
* 封面图修正自周星驰电影《工夫》
* 参考文献以及链接:
[1] 最后的 Windows XP 退役
[2] Minesweeper Game World Ranking
[3] 更详细的扫雷教程可以点击浏览 Strategy - MinesweeperWiki，对更具体的细节感兴致的，可以浏览扫雷游百思特网戏有些什么技能吗？ - 张砷镓的答复 - 知乎
[4] Minesweeper and logical circuits
[5] 要成为扫雷高手，先练好逻辑吧 - Albert_JIAO，果壳
[6] Quad-Core Redstone Computer - YouTube
[7] 什么是P问题、NP问题和NPC问题，以及怎么懂得 P 问题和 NP 问题？- 知乎
[8] 布尔可满足性条件 - 维基百科
[9] Circuits, Minesweeper, and NP Completeness - Richard Carini
[10] S R Broadbent and J M Hammersly,Percolation processes. Proceedings of the Cambridge Philosophical,1957,53 :629-641.
[11] Percolation - wikipedia
[12] Minesweeper as a Constraint Satisfaction Problem - Chris Studholme
[13] The Minesweeper game: Percolation and Complexity - Elchanan Mossel
[14] emoji - minesweeper - muan, github
[15] 看B站学物理：扫雷里的相变 - 梁昊，知乎