要成为扫雷高手,先练好逻辑吧

标签: 数学 计算机科学 原创 扫雷 逻辑电路 | 发表时间:2011-08-14 09:28 | 作者:Albert_JIAO Blacat
出处:http://songshuhui.net

扫雷作为策略游戏,需要游戏者精确的判断。现在扫雷高级的官方最快纪录是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完全问题。由此看来,面对一个上千上万个格子的巨型雷区,不要说去完成所有扫雷任务,就仅仅判断它是不是可解的,都可能会是计算机也承受不了的的大难题。

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

相关 [扫雷 高手 逻辑] 推荐:

要成为扫雷高手,先练好逻辑吧

- Blacat - CNBETA
扫雷作为策略游戏,需要游戏者精确的判断. 现在扫雷高级的官方最快纪录是33.95秒,中级则是由一个波兰玩家保持的8.5秒. 而初级纪录是1秒,世界上很多人达到了这一点. 在1秒的时间里完成初级扫雷,据测算概率在0.00058%至0.00119%之间(属于运气题),最可能的方法是直接点击四个角的方块.

真正的高手,相信逻辑而不是现实

- -
一、归纳法总结出的规律不一定正确. 通常,人们在使用归纳法时,往往会先设定一定的参照. 而从人类的思考惯性出发,这种参照往往是空间或时间. 所谓空间性归纳,简单来说,就是人们会默认在某个空间内有效的规律,在其他空间甚至在全部空间中也是有效的. 就好像一个创业者在某一个区域市场上获得了成功,就会想当然地认为自己在其他市场上也可以取得成功.

逻辑入门

- snowflip - Pure Pleasure - Reborn
你好,笑来,我想我问关于逻辑学方面的书籍有什么比较值得推荐的吗. 其实,我总觉得很多人缺的不是逻辑训练,而是“自省”训练,以及“道义”教育. Beyond Feelings,这是我当年的启蒙书籍(是我边读边敲做成电子版的). 想明白(系列)分类里的文章,建议你看看. TTC出过一个24讲的”Argumentation”,到Google上搜索“TTC+Argumentation”就可以找到.

苹果的逻辑

- Jacky - It Talks-魏武挥的blog
玩iPad也有大半年了,有一件事我一直不会,那就是删应用. 我知道长按一个图标会出现一个大叉,点击这个大叉能有“删除”的功能. 但我一直疑惑的是,究竟是删除了这个图标呢,还是真地删除了这个应用. 由于iTunes会同步应用回去,在我删了几次并被同步回去以后,我便一直认定,这只是在删除图标,就像windows桌面上删除一个快捷一样(我同步iPad一般是在睡觉的时候让电脑自己干,故而没有认真观察过).

周报的逻辑

- Shell Wang - 坏脾气的小肥
最近新同事加入很多,按照我的要求,入职半年内需要发送周报给我,半年后自己选择是否仍需发送. 行业内可能大部分的人都认为,周报就是流水账,是主管显示权力的手段. 最后还就真把它给搞成了一封流水账,或寥寥数语. 在职场中,有一条冷酷定律,叫做“如果主管不知道你做了某件事情,相当于你就没有做过这件事情. ”听上去不近人情,其实完全符合实用逻辑.

“脏话”的逻辑

- 星云 - 左岸读书_blog
脏话属于避讳之词,因此书面资料对说脏话的起源记录也很少,即使现在,很多词典也并不收录不敬之词,人们自然也没有多少关于说脏话的研究. 心理研究者认为,说脏话和孩子的啼哭很相似. 在幼儿时期,哭叫是一种可以接受的表达情感和释放压力和焦虑的方式. 随着儿童的长大(特别是男孩),西方社会的文化并不鼓励他们哭喊,特别是在公共场合.

足球的逻辑

- Race forward! - 学而时嘻之
最近看世界杯有感,本文试图提供一个关于现代足球的“统一理论”. 我并不是一个真正的球迷,但进行了一点思考,查了一点资料,不吐不快,乃做此文. 这个理论不是什么标新立异的一家之言,而是想从客观科学的角度,谈谈现代足球应该怎么踢. 我将避免零碎的规律总结,而是尽量使用逻辑推理的办法去“推导”这套理 论,且看我说的对也不对.