首页 >> 数学 >> 计算机科学 >> 文章

扫雷作为策略游戏,需要游戏者精确的判断。现在扫雷高级的官方最快纪录是33.95秒,中级则是由一个波兰玩家保持的8.5秒。而初级纪录是1秒,世界上很多人达到了这一点。在1秒的时间里完成初级扫雷,据测算概率在0.00058%至0.00119%之间(属于运气题),最可能的方法是直接点击四个角的方块。而本文所作的事情,则是将雷与雷之间的规律给你揪出来,并且深入思考其中的内涵。让你以后面对扫雷时,缩短与记录的差距,战无不胜!

 

从简单雷区入手

下图是一个初级的雷区,并且标注了两颗雷的位置,你能将剩下的地雷扫描出来吗?


经过逐一排查,可以很轻松的确定雷区中的6颗地雷所在位置:


再来看一个简单的“雷区”:


通过逐步扫描每一个方块会发现:首先最左边的和最右边的两个格子都一定是地雷,从左数第二个空格子和从右数第二个空格子也都是地雷,由于数字1的关系,从左数第3个格子和从右数第3个格子都不是地雷,翻开一定是数字1……这样一直下去,最后你会发现最中间的两个空格子,不管有没有地雷,都和周围格子上的数字不符。也就是说这样的雷区有bug,是无解的。

雷区中的逻辑门

怎么判断一个雷区是否有bug?又怎么判断雷区中地雷的具体位置呢?难道一定要从头到尾将雷区扫描一遍吗?

其实这些雷区里其实藏着一个规律。我们用数学方法来分析了上例的雷区:

在之前提到的这两个雷区里,把还没有翻开的格子交叉标记上字母x和x’。可以看到:当x的格子有雷时,x’格子一定没有地雷,反之亦然。如果将最左边的空格子作为输入,把最右边的格子作为输出,输入结果和输出结果一定是一样或者相反的。如果是相反的,这相当于一个NOT(“非”)门电子元件。如果是一样的,就有趣了,这样的一片雷区就具备了电路导线的性质!

在这里,雷区被看成了一个数字逻辑电路。执行这些“或”、“与”、“非”等逻辑运算的电路则被称为——逻辑门。任何复杂的逻辑电路都可由这些逻辑门组成。

逻辑门是集成电路上的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种型号的高低电平在通过它们后产生信号。而高低电平可以分别代表逻辑上的真假或二进制中的0和1,从而实现逻辑运算。具体到扫雷游戏里,也就是说,逻辑门可以用于判断一系列格子中的地雷的具体位置,而且它如同电路传导一样,精确而迅速。

常见的(也是扫雷中用到的)逻辑门包括“与”门、“或”门、“非”门等。将它们组合使用就可以实现更复杂的运算——完成复杂情形下的扫雷,这种方法比按照规则缓慢推进的扫雷方法要节省很多时间。

复杂雷区中的精确判断

在简单的雷区中小试牛刀后,带着发现的规律,让我们进行一次实战演习。下图是高级扫雷游戏中的一个典型的雷区:

你能在不翻开格子的情况下,直接指出黄格子中有无地雷吗? 如果将雷区随意改变一点——左上角的一个格子下移一位,结果又如何呢?


你可能需要考量全局,从某个点开始逐步推理,将雷区全部扫描一遍,才能判断。而当雷区任意改变一点时,你都要重新来过,才能再次解答。这无疑是一种巨大成本负担。

实际上我们可以很快速地给出答案:第一个雷区的黄格子中无雷。而第二个雷区的黄格子中一定有雷。

这是怎么做到的?其实将上述的逻辑门引入到这个复杂的雷区中,一切都会变得简单而清晰起来。

雷区内靠近边界、可以直接确定是地雷的位置都插上了标示旗,剩下的位置标上了不同的字母。把一个有地雷格子看作1,没有地雷的看作0。最左面的格子(u、v)作为输入,最右面的格子(t)作为输出。按照扫雷游戏的规则,经过一步步推算,它们之间的关系就是:

( u , v , t ) = ( 1 , 1 , 1 ) 或 ( 1 , 0 , 0 ) 或 ( 0 , 1 , 0 ) 或 ( 0 , 0 , 0 )

显然,这个雷区被归纳成了一个AND门,它不仅轻松化解了这个扫雷难题,而且把雷区的规律揭示出来了。如此一来,当你掌握扫雷中这些逻辑门规律并加以练习后,就能够达到精确、快速的“机械化”扫雷水准。而到那时,一个新纪录或许就会诞生了。

数学家的扫雷研究

将扫雷问题抽象化从而缩短游戏时间的人,也不仅仅是扫雷发烧玩家。一些数学家也十分关注这个游戏背后的数学意义。

英国一位数学家用扫雷游戏中的逻辑规律构建了一系列电子元件,用电子电路模拟雷区。他试图将一个的给定的雷区图案交由计算机来判断是否可解。如果随着格子数量的增加,电脑的计算量增长不是很快,就是P问题,如果计算量增加的很快,就是NP完全问题。计算机判断雷区是否可解,需要这类问题属于P问题才可以。

对于几种基本的电路元件(AND、OR、NOT),如果将很多个这样的元件组合起来,相互连接,就会产生很多个输入、输出口。判断最后哪些输出结果可以产生,哪些不可以产生的这类问题,被称为SAT问题,它属于一个经典的NP完全问题。

而英国数学家的这个问题在一些时候等同于一个复杂电子电路的SAT问题,也就是NP完全问题。由此看来,面对一个上千上万个格子的巨型雷区,不要说去完成所有扫雷任务,就仅仅判断它是不是可解的,都可能会是计算机也承受不了的的大难题。

本文已发表于果壳网 死理性派主题站 《要成为扫雷高手,先练好逻辑吧》

0
为您推荐

97 Responses to “要成为扫雷高手,先练好逻辑吧”

  1. 老资产阶级说道:

    图片全市叉。。。囧,难道是我电脑问题?

  2. celiaczy说道:

    图片全为叉叉,非常抽象……

  3. 何欣说道:

    是 啊 全市 ×

  4. asahi说道:

    图床挂了。

  5. biohu说道:

    图片全挂。。。

  6. Sandox说道:

    最爱扫雷。。。所以此文不得不评~

  7. ayanamist说道:

    看来果壳的防盗链没把松鼠会放到白名单里啊,哈哈

  8. 春雨后的蟹说道:

    极度抽象啊!!!!!!

  9. Kirby Zhou说道:

    图片全挂啊
    有原文链接么

  10. seeyougogo说道:

    图片看不到啊啊啊!!!

  11. 爱柚子说道:

    啊.图片XX了.

  12. netson说道:

    图挂了?

  13. a说道:

    Shift+XYZZY才是王道撒……

    • hypermania说道:

      同感。。。曾经用这招忽悠过同学。。。。说解决这类问题有个一般方法。。。。

  14. 游识猷说道:

    抱歉,图片已经更新,现在看得到吗?

  15. Alvan说道:

    如果扫雷只要能标出所有雷就算赢的话,那这个方法确实很有帮助。不过扫雷的游戏规则是点出所有非雷区,哪怕一个雷都不标注也行——结果就是在这个电路中,“电流”的速度就是你手指点击非雷区的速度。所以,你跟世界纪录之间的差距,仅仅差在一个更快速的手指和一个更精准的鼠标。

    • 中子豆说道:

      分析判断速度也很难提高的。
      我最好结果是146s,看过一个41s搞定的视频,真的是太NB了,自愧弗如。
      不过我教给大家一个阴招,可以用来炫耀:
      修改注册表,把扫雷记录改成一个很小的数字,然后就可以让计算机盲羡慕一把了。

  16. 林秋说道:

    最早接触电脑,玩的就是简单的扫雷,却屡屡受败,后来玩了新玩意,新的东西一直出,旧的倒成了经典了。

  17. 学习雷区中的逻辑门

  18. 独角大仙说道:

    曾经一度迷恋扫雷,高级玩过30s……

  19. 喜羊羊和一休哥说道:

    最后一张挂了。我已经刷新不下十遍了。

  20. canny说道:

    离散数学?呃,那其实可以直接编一个指导程序.........

  21. winio说道:

    显然数据量对于人脑来说有点大了诶。。

  22. 夜风过耳说道:

    低级3秒蛋疼路过,其实到后来已经是机械思维了

  23. 美国VPS说道:

    本来就是娱乐 太认真的话就不行了。

  24. 护眼一号说道:

    太深奥了。

  25. 野线说道:

    我从来没过关过,,那位大侠告诉我怎么玩的啊!!

  26. ABCZ说道:

    太难明白了!

  27. 名無し说道:

    高级至今破不了120秒,初级破不了2秒什么的觉得自己真是弱爆了

  28. nathan_haitian说道:

    看完了,不明就里

  29. Izual_Yang说道:

    其实很多这类小游戏归根结底都是数学或者逻辑。
    目前用来杀时间的是ConFusebox 2

  30. misterhe说道:

    大家都来学习学习。成为扫雷高手。

  31. 拼音佳佳说道:

    空当接龙算是比较高水平的,怎么写?

  32. 陈毅说道:

    再写一遍吧,我还是看不懂!!

  33. 发光二极管说道:

    机械化的境界实在难以想象。。

  34. 陈毅说道:

    在高级图中为什么要有(u、v)两个输入,只用一个u或v不行吗? 什么时候开始使用t 呢? 如果只在输出的最后一格或两格可以吗? 这有什么特别的规律(或是“规定”)吗?

  35. 陈毅说道:

    这里所举的例子好像有点特殊。 能不能用真正的扫雷来做一遍,做个示范

  36. 子为说道:

    高级128秒飘过

  37. misterhe说道:

    U/V/T三个变量一起来就搞不明白了。

  38. c2blog说道:

    文章安这个题目真搞笑,有证据显示扫雷高手都是练过逻辑的吗?

  39. liansh说道:

    曾经想写个非暴力破解自动扫雷的程序,后来找了一下对于扫雷分析的文章,发现扫雷中并不是所有的地雷位置都可以通过数学推导,有些特殊组合必须靠蒙,然后果断放弃了写这个程序的想法。

    • xyz说道:

      在被地雷包围的几个点上存在着1个非雷区的时候,只能靠蒙
      记得有一局,我只剩下最后2个点,其中只一个是雷区,而我最终失败了.....

  40. 牙膏泡泡说道:

    看不懂呀

  41. 飘飘说道:

    有点飘啊

  42. 小程说道:

    为什么我能看到图啊?

  43. 3333说道:

    把电脑变慢,速度自然提高

  44. 蛤蜊3说道:

    (举手)老师请问在最后的高级雷区,造成黄色目标格最终输出的究竟是哪一个U跟哪一个V呀?!
    b1、b2等带编号的是什么? W坐标向右又是什么?
    我是来看科普的,但是依然看哭了呀……

  45. 天灵说道:

    这么快!我初级的最高纪录是6秒……中级的最高是90多……高级的要300多……恩……这是最快的……高级的有时候要500多秒……囧里个囧,话说那个1秒是怎么点的啊……多么的眼疾手快……

  46. In The End说道:

    看不懂。。。。
    太深奥了。。。。。。。。。

  47. 陈杰锋说道:

    不明白啊!!!

  48. CH说道:

    没有必要这么玩吧,一块一块推就好了。

  49. 珍珍说道:

    注定数学0分啊~~·看起来好吃力··初级的扫的差不多了··但是到最后还是踩到那该死的shi~~~哎!!!

  50. 古德莫宁说道:

    复杂雷区中的精确判断 这一部分重写一遍吧,不明白最后怎么得出结论的,把标注字母和一步步推算的过程写一下啊,把精华的部分给漏了

    • SillyDaddy说道:

      这个可以根据平时扫雷的经验推出来吧,就像扫雷时用?标注不确定是不是雷的位置一样,只不过现在用一个逻辑变量来表示一个不确定性。
      给个链接吧,文章中提到的英国数学家应该指的就是他——R.W.Kaye,在他的网站上应该可以找到你想要的东西:http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

  51. qq说道:

    最高记录,中级30秒内,高级100秒内。初级1秒是完全可能的,纯属运气了

  52. Catcatcher说道:

    世界纪录也要靠运气..表示对这种有很大可能点两下就死的游戏木有耐心...

  53. 广州学生说道:

    以前在学校机房上课的时候,无聊经常玩这个游戏,玩到困难那关基本上是挂了。也没想这么多逻辑的东西。

  54. lyem说道:

    写得不好。

  55. 刘姝说道:

    看不懂!

  56. erry说道:

    这不是写给只有数学初级知识的人看的,后面那张高级图很难看懂:(

  57. 陈龙腾说道:

    我out了

  58. 咕噜噗说道:

    很喜欢 明天有时间按你说的看看

  59. 张山鹰说道:

    你知道扫雷网吗?这个八月是疯狂的。
    你的推导的确不太像科普文章啊!

  60. 晓风残月说道:

    很简单的.......天书

  61. 99说道:

    高级92秒的飘过

  62. Amb说道:

    每个块只有两种状态的SAT也就是2-sat是P问题啊,可以线性时间搞定

  63. 外贸研究网说道:

    真牛的啊!

  64. 李嘉瑞说道:

    效率挺高的

  65. 宋晨晨说道:

    这都能算?

  66. 板砖说道:

    完全看不明白,太深奥了,不过很讶异这东西是能计算的

  67. AAA说道:

    根本不实用的东西。你要把那些u,v标出来的时间要多长?除非写程序来解决,否则这种讨论毫无意义。

  68. marktrue说道:

    我表示……对于XP的扫雷……可以通过先点开一个格子,然后迅速最小化,然后用任务管理器中的“切换至”切换到扫雷,这样计时器就会停下来,所以……我的XP上的各级扫雷记录都是1s……

  69. graylong说道:

    哈哈 楼上的回答正解。。确实是1s 疯狂啊

  70. 江户川说道:

    这个有点儿深奥```` 要是在讲细一些就好了,我可是个雷盲啊!

  71. www.zls365.com说道:

    厉害,连这都可以

  72. ljfriend说道:

    使用win+d和xyzzy的飘过。

  73. 草莓挞说道:

    需要N分钟的表示鸭梨很大

  74. 王秋硕说道:

    哈哈 还不如在重新来一盘。

  75. 板砖说道:

    高级的记录64秒.弄的我好苦,眼睛受不了

  76. 红烧开水说道:

    我没文化,我看不懂。我就来嘲笑一下。
    你们写的东西别人都看不懂。
    那你们还写这种东西做什么?
    假如真的想要科普的话,先练好逻辑来写文章吧。哇哈哈哈。

  77. 红烧开水说道:

    大致上来说。你们这帮人想问题还可以。
    但是你们没有足够的总结能力。总结下啊?什么都没有。
    最后还放出个外国人的东西说,别人好厉害。就这样完了?虎头蛇尾。真好笑。

  78. 老万说道:

    高级扫雷本人都26秒了

  79. 21说道:

    没看明白

  80. 文刀嗣说道:

    哈哈,上周刚刚读过Charles Petzold先生的《code》(编码—隐匿在计算机软硬件背后的故事),里面提到许多逻辑门,除了Albert_JIAO在这里所述的三种简单逻辑门(OR、AND、NO)外,稍复杂一点的还有或非门NOR、与非门NAND、同或门XOR。
    但这里要是把“按照扫雷游戏的规则,经过一步步推算”的推算过程说的清楚点大概就OK了。

  81. 企鹅说道:

    表达不清,门电路如何扫雷?

  82. dragerleo_7kn说道:

    这太变态了,我的初级最快都要3秒,中级是29秒,高级是98秒.我自己都再也打不破这个纪录了,不知道那些人是不是神,能点那么快?

  83. 小李飞刀说道:

    话说当年我的扫雷高级的记录是80秒,当然有点儿运气的成分了,一般来说平均在100-120秒,现在已经明显退化了,估计要在180秒左右了

  84. ttttt说道:

    ”下图是高级扫雷游戏中的一个典型的雷区:“ 引用的是一个如此对称的雷区, 胆敢说是一个典型的雷区,随机生成的雷区不可能这么对称。排雷所花的时间取决于你的鼠标垫的好坏,鼠标的好坏,判断的快慢(通常的鼠标一次按下并弹起所需要的时间是0.20--0.22秒)当你的能力越来越强的时候,鼠标垫和鼠标的性能就越来越重要了,就像跑鞋对于百米赛跑运动员的意义一样

  85. 张坤说道:

    我的天啊,简单的扫雷竟然转化到逻辑电路模型....

  86. sa说道:

    渣文吧这是,敢问作者真的扫过雷吗?没点开前就已经把数字全标识出来的扫雷游戏,还叫扫雷?
    纯为了把门电路和扫雷绑一起才编造出来的吧?

Leave a Reply for SillyDaddy