要成为扫雷高手，先练好逻辑
我的图书馆
要成为扫雷高手，先练好逻辑
扫雷作为策略游戏，需要游戏者精确的判断。现在扫雷高级的官方最快纪录是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完全问题。由此看来，面对一个上千上万个格子的巨型雷区，不要说去完成所有扫雷任务，就仅仅判断它是不是可解的，都可能会是计算机也承受不了的的大难题。
发表评论：
TA的推荐TA的最新馆藏[转]&要成为扫雷高手，先练好逻辑吧 | 科学人 | 果壳网 科技有意思
要成为扫雷高手，先练好逻辑吧
要成为扫雷高手，先练好逻辑吧。如何成为扫雷游戏高手。
本文作者:Albert_JIAO
扫雷作为策略游戏，需要游戏者精确的判断。现在扫雷高级的官方最快纪录是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完全问题。由此看来，面对一个上千上万个格子的巨型雷区，不要说去完成所有扫雷任务，就仅仅判断它是不是可解的，都可能会是计算机也承受不了的的大难题。
你可能感兴趣
所以所有的残局理论上都能扫出来什么的么
信息安全专业，物理爱好者
引用暴走紫罗兰的回应：所以所有的残局理论上都能扫出来什么的么不，最后结论是，这是一个NP问题，计算机都无法判断是否能解出来，我们更无法判断。只是“知道能不能解”和“能不能解”是不是一个问题
不会玩的飘过·····
不是说”计算机无法判断“，只是得出解的时间是不可忍受的
同3L。。。
从来扫雷一踩一个炸的路过- -0
机械电子工程、消费产品设计专业
用逻辑分析过的各种形状，作为定式记下来，然后速度就快了。
没看懂0.......什么意思
加州大学经济学专业
本质上来说也不是逻辑，而是熟能生巧。
引用evan的回应：这位同学的解释有些问题P问题是说在多项式时间内能够确定某个解是否正确NP问题是说无法在多项式时间内求解-----------------------------正解
P问题指的是能够在多项式的时间里得到解决的问题NP问题指的是能够在多项式的时间里验证一个解是否正确的问题NPC问题指的是：首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。NPH为题指的是：满足NPC第二条但不满足第一条的问题本文所指这个问题是NP中的NPC，是一种尚未在多项式时间内找到解法的问题，证明或推翻NPC是否有多项式时间解法，即是信息学中知名问题“P=NP？”。= =所以本人觉得本文最后一段有问题...2L,4L,12L发言也有问题...
在已经点出来的地方同时按鼠标左右键可以判断对角线有没有雷，这可以大大提高胜率吧
最后吐槽一句NP并不是NON-POLYNOMIAL！
更多链接看这里：
顶，扫雷进入一个平台期不能刷新纪录了。。。数独也是
会数独 不会扫雷啊
科幻死忠奇幻迷，吉他诗人，摄影爱好者
有意思~我们寝室有个V5的孩子玩扫雷把鼠标右键废了……
科学松鼠会成员，信息学硕士生
Solapras这个说得对……NP不是Non-Polynomial啊，是Nondeterministic Polynomial啊……另外，任何P中的问题，都是NP中的问题……要证明一个东西难，光证明它是NP是没用的……要证NP hard……不过这些概念太抽象了，估计即使死理性派写出来了也没人看……
平台期+1得突破突破。。
概念游戏了哇！！！
语言爱好者
引用暴走紫罗兰的回应：所以所有的残局理论上都能扫出来什么的么否，比如下面这个（这是雷区的左上角）：? ? @1 3 @0 1 1，?表示未翻开的格子。
引用Solapras的回应：P问题指的是能够在多项式的时间里得到解决的问题NP问题指的是能够在多项式的时间里验证一个解是否正确的问题NPC问题指的是：首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。NPH为题指的是：满足NPC第二条但不满足第一条的问题本文所指这个问题是NP中的NPC，是一种尚未在多项式时间内找到解法的问题，证明或推翻NPC是否有多项式时间解法，即是信息学中知名问题“P=NP？”。= =所以本人觉得本文最后一段有问题...2L,4L,12L发言也有问题...恩，这是正解，我4L的发言是错误的因为无法编辑回复，为了防止前面的发言误导人民群众，删除该条留言
常常是最后一个雷必须靠运气啊……
扫雷的时候最讨厌碰到左看右看都确定不了的“田"字形了
编辑好运气，点这么多也没被炸，我从没点出过高级来。
扫雷高级最快65.99的家伙表示这个逻辑门太麻烦了吧。。
不太明白， 平常玩扫雷的时候，没想这么多吧，而且楼主给的案例都是对称的，当然好计算输入输出什么的额。但我们平常玩的哪有这么好的模型啊。一般的是碰运气先乱点几个，开了一片空白区，在逐个分析推倒的吧.....
引用hxaohan的回应：在已经点出来的地方同时按鼠标左右键可以判断对角线有没有雷，这可以大大提高胜率吧握手，双键齐下的扫雷党表示毫无压力~~
表示没看懂...
显示所有评论
(C)2016果壳网&&&&京ICP证100430号&&&&京网文[-239号&&&&新出发京零字东150005号&&&&
违法和不良信息举报邮箱：&&&&举报电话：很抱歉，您访问的部落不存在
您可以试试：