扫雷技巧|玩扫雷还有什么技巧？( 三 )

难过
稍微值得庆幸的是，在我们平时玩的比较小的棋盘下，计算机还可以通过搜索得到答案。
为了了解计算机处理问题难度的几个级别，有必要先知道一个概念——多项式时间。对于同一个算法，根据处理问题大小的不同，计算机一般来说需要不同的时间进行计算。用最直观的例子来说，小明要去洗衣服，他洗 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 ，菱形为高级，