江苏龙网

  1. 主页 > 生活百科 > >

玩扫雷还有什么技巧？ 扫雷攻略( 二 )


图中黄色部分是典型的扫雷问题，需要猜 。根据角落的数字，只能知道12的黄色部分一定只有一个雷，但不知道哪个是雷 。如果没有其他信息，我们努力了大半个棋盘，最终通过这个雷区的概率仍然只有1/8 。
这个简单的判断是可以的，有时候会有一些比较隐晦的猜测 。
扫雷判断题
假设我们在扫雷过程中遇到这样的模式，那真的是欲哭无泪的事情 。如果你不知道怎么哭，你可以先准备好眼泪，边肖会马上告诉你为什么要哭 。。。从左边开始，假设第一个空位有雷，那么第二个空位没有雷，因为空位的中间1存在，第三个空位有雷，以此类推 。但如果第一空位没有雷，第二空位有雷，也是有道理的 。我要踩地雷了，还有这么复杂的问题，至于嘛 。。。
别急，后面还有更复杂的事情 。这里的X和下面的*上有没有雷的情况都是一样的，所以这个雷区就像是一根传递信号的电线 。在扫雷地图上，不仅可以制作这种简单的信号传输线，还可以实现所有电子电路中逻辑门的运算 。[4,5]
非门电路
或门电路
这是两个“简单”的逻辑门，分别实现翻转信号的非门和对两个信号进行或运算的或门 。在另一款知名沙盒游戏《《我的世界》》中，玩家也可以利用游戏中的材料——红石(实际上在此之前的Windows 10操作系统每年的更新代码都是以红石命名的)，实现各种复杂的逻辑运算，也有玩家已经在《我的世界》用红石打造出了真正可操作的电脑 。。。
具有完整寄存器、加法器和其他部件的Redstone计算机[6]
算了，我不敢想象扫雷会变成什么样 。。。
很难判断有没有解 。
找答案
回到文章开头，如果我们解决了一个扫雷问题，我们就很容易死掉 。如果我们把这个问题交给计算机呢？遗憾的是，在正常情况下，计算机仍然无力解决扫雷问题 。。。
困难的
好在在我们平时玩的比较小的棋盘下，电脑也可以通过搜索得到答案 。
为了理解计算机处理问题的几个级别的难度，有必要先了解一个概念——多项式时间 。对于同一个算法，根据问题的大小，计算机一般需要不同的时间来计算 。举个最直观的例子，小明要去洗衣服 。他洗一件衣服用2分钟，洗五件衣服用10分钟，洗十件衣服用20分钟 。处理问题的时间随问题规模线性变化，是线性多项式 。现在假设小明还是要洗衣服的，只是现在的衣服比较特殊 。这种衣服他洗一件需要2分钟，但是洗五件的时间变成了32分钟，洗十件的时间变成了1024分钟 。这个时间是指数的而不是多项式的 。它是评价一个算法的一个非常重要的指标 。随着问题规模的增大，如何增加计算时间 。
在计算机中，我们仍然认为多项式时间是很快的 。如果按照解决的难易程度对问题进行分类，P指的是多项式时间就能解决的问题，俗话说的好，是能快速解决的问题 。NP指的是一个计算不一定很快的问题，但是我们可以很快查到任何答案 。完全NP问题是比所有NP问题都难的NP问题 。人虽然有一个奇妙的想法，但总认为计算会很快，应该能找到让他快速计算的方法，但目前还是未知数 。。。[7]
不幸的是，求解一个扫雷游戏的解，恰好是一个NP完全问题——在能够轻松验证结果正确与否的问题中，难度最大的一个 。到目前为止，人们还没有找到这类问题的多项式时间算法，通常只有指数甚至阶乘搜索算法才能解决 。
显示LCD数字的逻辑电路 。我们可以很容易地一个一个尝试，但是反过来就很难了，尤其是当逻辑电路非常大的时候 。
扫雷游戏就是这样一个难题，因为上一章提到过，扫雷游戏可以看作是一个用逻辑门进行运算的逻辑电路 。给定一个逻辑电路，在输出结果已知的情况下，能否确定每个输入的值？这个问题叫做SAT问题，是世界上第一个被证明是NP完全的问题 。[8]这种问题很容易验证 。你只需要把结果代入逻辑电路，马上就能知道是否符合要求 。但是逆向计算符合结果的输入是极其麻烦的 。
求解扫雷游戏的结果，利用那些构造的逻辑门，就相当于求解SAT问题 。[9]
扫雷也与渗透有关 。
预膨胀
液体，图片来自Giphy，Michael Shillingburg
其实我们觉得玩扫雷游戏很难 。其实还有一个原因 。这个原因和物理学中的渗透有关 。
20世纪60年代，科学家[10]发现当流体流经多孔介质时，介质中的空孔洞总会被堵塞，有时会影响流体的流出 。奇怪的是，当这些多孔介质中随机堵塞的孔隙比例逐渐增大到一定值时，开始时还能流动的流体突然被完全堵塞 。当孔洞被随机堵塞的概率发生变化时，液体流动的速率也会发生突变 。


推荐阅读


上一篇：省控线是什么意思 本科一批省控线什么意思

下一篇：“鬼斧神工”不能形容天然景物 鬼斧神工是什么意思