数学家的扫雷研究
将扫雷问题抽象化从而缩短游戏时间的人,也不仅仅是扫雷发烧玩家。一些数学家也十分关注这个游戏背后的数学意义。
英国一位数学家用扫雷游戏中的逻辑规律构建了一系列电子元件,用电子电路模拟雷区。他试图将一个的给定的雷区图案交由计算机来判断是否可解。如果随着格子数量的增加,电脑的计算量增长不是很快,就是P问题,如果计算量增加的很快,就是NP问题。计算机判断雷区是否可解,需要这类问题属于P问题才可以。
对于几种基本的电路元件(AND、OR、NOT),如果将很多个这样的元件组合起来,相互连接,就会产生很多个输入、输出口。判断最后哪些输出结果可以产生,哪些不可以产生的这类问题,被称为SAT问题,它属于一个经典的NP完全问题。
而英国数学家的这个问题在一些时候等同于一个复杂电子电路的SAT问题,也就是NP完全问题。由此看来,面对一个上千上万个格子的巨型雷区,不要说去完成所有扫雷任务,就仅仅判断它是不是可解的,都可能会是计算机也承受不了的的大难题。