复杂雷区中的精确判断

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

如何去做

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

如何去做

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

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

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

看成电路就好分析了

　　雷区内靠近边界、可以直接确定是地雷的位置都插上了标示旗，剩下的位置标上了不同的字母。把一个有地雷格子看作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完全问题。由此看来，面对一个上千上万个格子的巨型雷区，不要说去完成所有扫雷任务，就仅仅判断它是不是可解的，都可能会是计算机也承受不了的的大难题。

编辑：大天使