扫雷技巧口诀( 三 )

不幸的是，到目前为止，还没有找到多项式时间算法来解决像求解一个扫雷游戏的解，正好是一个 np完全问题——在能够轻松验证结果是否正确的问题里面比较难的那一类。,这样的问题，通常只使用指数甚至阶乘搜索算法来解决它们。
液晶数字显示逻辑电路。我们可以很容易的一个一个的尝试，但是反过来就很难了，尤其是逻辑电路很大的时候
扫雷游戏就是这样一个难题。原因在于上一章提到的扫雷游戏可以看作是一个由逻辑门操作的逻辑电路。给定一个逻辑电路，在知道输出结果的情况下，是否可以确定每一个
输入值？这个问题叫做sat问题，是上第一个被证明其为 np完全的问题.[8]这种问题很容易验证。你只需要把结果代入逻辑电路就可以立刻知道是否满足要求，但是反过来，计算满足结果的输入是极其麻烦的。
解决扫雷游戏的结果，使用那些构造的逻辑门，相当于解决sat问题。[9]
扫雷还和渗透有关系
预编码
液体，图片来自迈克尔希灵堡的吉菲
其实我们觉得玩扫雷游戏很难，但是还有一个原因。这个原因和物理学中的渗透有关。
在20世纪60年代，科学家[10]发现，在在流体流过多孔的介质的时候，介质中的空洞总是会被堵塞，有时候就会影响流体流出。更奇怪的是，当这些多孔介质的孔隙比例逐渐增加并达到一定值时，比较初能够流动的流体突然被完全阻塞。当孔洞被堵塞的概率随机变化时，流经的液体比例也会突然变化。
这种现象被称为逾渗.[11]
在这种情况下，你应该如何开始
在在扫雷里面，也存在类似逾渗的现象。,当游戏中的地雷密度极低时，我们几乎是漫不经心地指出，我们不会指向地雷，而是指向大片空白区域，并立即解决问题。但当地地雷密度增加后，即使我们理性分析，绝不瞎猜，也不可能正确排雷。
根据棋盘大小不同，有人计算了不同雷密度下的获胜概率。三角形对应的曲线是主88，正方形1513，菱形3016 。其实这里的解不包括第一次随机就踩雷的概率。[12]
当我们抽象出流体通过多孔介质的渗流模型时，其实对应的是点渗流，即我们把整个介质想象成一个网络，当流体通过每个网格时，有一个概率p可能通过。如果不能流过的网格在网络中连成了片，流体就不能流过了。
不严格来说，解决扫雷问题其实和渗流模型很像，解决的过程其实就像推土机一样,不断利用现有的知识把已知的区域一层一层往外推。如果游戏中某处雷的密度较高，则可解部分更有可能被雷分开，地雷密度和逾渗参数起到了一样的作用.如果被分开无法连接整个棋盘，则无法继续推理。更严格的证明可以参考埃尔查南莫塞尔的论文。[13]
推土机，图片来自网络
随着电网的不断扩大，胜利曲线的中间部分变得越来越陡，扫雷问题日益发展到两个极端：在要不就根本解不出来，要不就是很容易地就能解出来。,的先进模式中，地雷的密度实际上已经达到99/480=0.2，被解决的概率不到1/4，这与手抖一点也没有错，而且开局不利重新开始确实不友好。
结论
结论
表情版扫雷[14]
相信看到这里的人
跃跃欲试一定想玩扫雷。
我相信你。
世上无难事，只要肯放弃
【扫雷技巧口诀】卸载即可。