有时候，小编回想起童年和青春，眼前总会浮现出一片碧蓝碧蓝的天空和嫩嫩的水草，以及过去和朋友们在上面度过的快乐时光……

当然，别误会我

这就是我所说的蓝天和草地

为了防止被撞，小编提前选择爆头蹲防

Windows XP确实有很多内存，而且XP是一个真正好用的系统。Windows XP于2001年8月24日正式发布，微软于2014年4月8日停止支持Windows XP桌面，直到本周二，2019年4月9日，最后一批运行在嵌入式设备上的Windows XP失去了微软的官方支持。XP们终于正式跟我们说再见了。[1]

经典的扫雷游戏

说到XP，该操作系统的经典游戏，如扫雷和纸牌游戏是经典的，有趣的和耗时的。如果你能计算全人类花在这上面的时间，那将是一个天文数字……但是，尽管《扫雷》已经玩了很长时间，而且玩了很多次，我猜99%的玩家都没有想过在玩《扫雷》时死亡是多么容易……

比较一下其他孩子玩扫雷的速度

画面被加速了。如果你想看世界上最快排雷的真实记录，请查看[2]

再看看我自己玩扫雷……

大概就是这个水平了。我点击扫雷图标，地雷就爆炸了

XP已经过时了，但幸运的是，对于Windows 10，你仍然可以直接进入商店中的“扫雷”并下载正式重启的扫雷游戏。

事实上，扫雷是许多科学家喜欢玩的游戏。但大多数玩《扫雷》的人如果死得很快，他们就会反复开始，直到获得一个好的开始(然后很快死亡)。另一方面，如果科学家在玩扫雷游戏时很快死亡，他们就不会重新开始，他们只会证明“这款游戏完成的可能性为零”。

毕竟扫雷已经有这么长的历史了，有很多论文分析扫雷游戏的概率。作为一个熟练的点击扫雷重启按钮手残扫雷玩家，今天我就和大家系统的聊聊扫雷背后的故事。

扫雷的秘密

Minesweeping cheat sheet

天下武功，坚不可摧，唯快不破!

从数学上讲，扫雷是一个给你一个给定的条件，然后一遍又一遍地解决它的过程，就像一个不断增加条件的文字问题。你可以通过左键点击block并右键点击你认为是Thunder的区域来确保block不是Thunder。如果你点击一个不是雷的区域，它会告诉你在该区域周围的8个空间中有多少雷。如果你按得够快，雷抓不到你。

通过一个非常简单的反证法，我们可以推算出地雷的大部分位置。[]

角落里的情况

所谓反证法，就是把问题反过来想。如果你有一个缩进的角落，那里所有的东西都是空白的，但角落里有一个1，那么角落里一定有一个雷。因为如果这个地方不是雷，雷中间的我就得去流浪了……同样，如果你的一边是3，那么旁边的3一定是雷。毕竟，我的兄弟们不能挤进格子里。

在边界处

除了这种矛盾之外，扫雷还有许多固定的“套路”。学会这个套路，保证你的扫雷舰技能大大提高，杀死社区扫雷舰500人。

事实上，在扫雷时遇到一些固定数字是很常见的。例如，三个连续的数字是121。这个时候，不用多想，就可以直接在121的两个方向相反的方向标记地雷。或者四个连续的数字，1221，在这种情况下2朝上也一定是雷。

在121的情况下，由于左边的1，黄色区域只能有一个灰色，但是中间的2要求至少有两个灰色，所以粉色的一定是雷。在另一边做同样的事情

在1221的情况下，与上述证明过程相同，由于1的限制，黄色区域只能有1个灰色，因此与2正对面的另一个正方形必须是雷。

“小编小编，我有一个问题，121221?”根据填雷的秘密，在1个雷的中间靠近两个雷啊？”

“这种情况是不可能的!左边的三个地雷已经覆盖了上面所有未知的空间，所以最多只有三个地雷。但底部显示的是1,2,2,1,2,1，只有中间的五个细胞重复计数，它们都达到了7，是3的两倍多。所以这个图不可能存在!”

收回去吧。正如我上面提到的，扫雷确实有它自己的方法。如果你每天都学习这个秘密，随着时间的推移，你就会在扫雷中取得成功。

排雷全靠运气

幸运与否，这是个问题

当你玩《扫雷》时，你必须接受这是一款关于角色的游戏。

虽然生活已经如此艰辛，但我还是要无情地揭开这一点。这时候你一定已经掌握了扫雷的套路，但有时候你还是要处理猜雷的问题，如果走错了一步，整个游戏就输了……

猜猜黄雷是怎么分布的？

黄色部分是一个典型的扫雷谜题，需要猜测。根据角落里的数字，我们都知道黄色的1 2的区域里一定只有一条射线，但是我们不知道哪一条是射线。如果我们没有任何其他信息，我们仍然只有1/8的机会完成了这个区域的一半。

这种简单的判断很好，但有时会有更微妙的猜测。

扫雷问题

如果我们在扫雷过程中遇到这样的格局，确实是一件伤脑筋的事。如果你不知道怎么哭，你可以准备好你的眼泪。小编会告诉你为什么要哭。从左边开始，如果第一个空缺有雷声，那么第二个空缺就没有雷声，因为在空缺的中间有一个，所以第三个空缺就有雷声，以此类推。但如果第一个槽里没有雷，第二个槽里也没有雷，这就说得通了。我必须踩到地雷，这整个复杂的问题，至于……

别担心，还有更多。不管在x上打雷还是在*上打雷都是一样的，所以这个雷区就像一根传导信号的电线。在扫雷地图上，我们不仅可以用这种简单的导线来传输信号，还可以在所有的电子电路中实现逻辑门的操作。(4、5)

Non-gate电路

或门电路

这是两个“简单”的逻辑门，实现了一个翻转信号的非门和一个对两个信号进行操作的或门。在另一款流行的沙盒游戏《—— 《我的世界（Minecraft）》中，玩家也可以使用游戏的材料红石(实际上，在此之前，红石是以每年更新的Windows 10操作系统命名的)来实现各种复杂的逻辑运算，甚至更多的玩家在《我的世界》中使用红石来构建真正的工作计算机……

红石电脑具有完整的寄存器、加法器等组件[6]

算了吧，我甚至无法想象扫雷舰会是什么样子……

很难说是否有解决办法

Find solution

回到本文的开头，如果我们试图解决扫雷问题，我们很容易死亡。把问题留给电脑解决怎么样？不幸的是，总的来说，计算机目前还无力解决扫雷问题……

悲伤的

值得庆幸的是，计算机还可以在我们通常玩的小棋盘上搜索答案。

在计算机中，我们仍然认为多项式时间是快的。如果我们按照问题的难易程度对问题进行分类，P表示可以在多项式时间内解决的问题，也就是所谓的快速问题。NP是一个计算速度不一定快的问题，但我们可以快速检查任何答案。NP完全问题是比所有NP问题都难的NP问题。尽管人们有一个很好的想法，他们应该能够找到一种快速完成的方法，但这仍然是未知的……[7]

不幸的是，解决扫雷问题是最困难的np完全问题之一，可以很容易地验证其正确性。到目前为止，还没有找到多项式时间算法来解决这类问题，通常只有指数甚至阶乘搜索算法才能解决。

0

扫雷是一个如此困难的问题的原因是，正如前一章所提到的，扫雷可以被认为是一个逻辑电路，逻辑门在工作。给定一个逻辑电路，如果输出是已知的，是否可以确定每个输入的值？这个问题被称为SAT问题，是世界上第一个被证明是np完全的问题。这类问题很容易验证——你只需要将结果插入逻辑电路，就能立即看到它是否满足要求——但另一方面，计算满足要求的输入是非常麻烦的。

使用这些构造的逻辑门来求解扫雷的结果，完全等同于求解SAT问题。[9]

扫雷也与渗透有关

Precolation

液体，图片由Giphy提供，Michael Shillingburg

我们很难玩《扫雷》还有另一个原因。原因与物理学中的渗透作用有关。

在20世纪60年代，科学家们发现，当流体流过多孔介质时，介质中的孔洞总是被堵塞，有时会干扰流动。更奇怪的是，当这些多孔介质中随机堵塞的孔隙比例增加到一定值时，最初能够流动的流体突然变得完全堵塞。随着孔被随机堵塞的概率的变化，流体流过的速率也随之变化。

这种现象被称为预沉淀。[11]

在这种情况下你会怎么做

类似的渗流作用也发生在排雷过程中。当游戏中的地雷密度非常低时，我们几乎是随机点击，不是为了击中地雷，而是为了击中大面积的空白区域，这样问题就立刻解决了。但是，当地雷的密度增加，达到一定程度时，即使我们理性地分析，从不瞎猜，也不可能把扫雷问题解决好。

对于不同的棋盘大小，有人用不同的地雷密度计算了获胜的概率。三角形对应初学者的曲线为8 8，正方形为15 13，高级菱形为30 16。我们能否解决这个问题实际上并不包括在第一次随机点击时击中地雷的概率。12

当我们抽象流体通过多孔介质的渗流模型时，实际上对应的是点渗流，也就是把整个介质看作一个网络。当流体通过每个网格时，它能通过的概率为p。如果无法通过的网格在网络中被连接成碎片，则流体无法通过。

粗略地说，扫雷舰问题的解决方法与渗透模型非常相似，解决它的过程实际上就像一台推土机，不断地利用我们已有的知识，将已知区域逐层向外推。游戏特定部分的地雷密度越高，可解决的部分就越有可能被地雷分开，地雷密度和渗透参数也是如此。如果它是如此分离，它不能连接整个板，它不能继续推理。要获得更严格的证明，请参阅Elchanan Mossel的论文。[13]

推土机，图片来自网络

随着网格的增长，胜利曲线的中间部分变得越来越陡峭，扫雷问题也变得越来越极端：要么根本无法解决，要么非常容易解决。在高级模式下，地雷的密度实际上是99/480=0.2，解决它们的概率小于1 /4。更不用说你犯了一些错误，有一个糟糕的开始。

结论

Conclusion

表情符号版本扫雷[14]

相信这里的人

你一定很想玩扫雷

我相信你

世上无难事，只要肯放弃

卸载OK

0

*参考资料及连结：

最后一款Windows XP已经退役了

[2] Minesweeper Game World Ranking

关于更详细的扫雷教程，你可以阅读Strategy-MinesweeperWiki。对于那些对更具体的细节感兴趣的人，你能读一下扫雷有什么提示吗？-砷镓-知乎的回答

[4] Minesweeper and logical circuits

[5]要成为扫雷高手，首先要练习逻辑——焦国肯

[6] Quad-Core Redstone Computer - YouTube

什么是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

从B站研究物理：扫雷舰的相变-梁浩，知湖

编辑：Cloudiiink