扫雷作为电脑自带的小游戏广为人知,但在数学和计算机研究中也曾成为话题。关键词是“NP完全”。
扫雷是NP完全问题
2000年前后,据说数学家理查德·凯(Richard Kaye)证明了,与扫雷有关的下面这个问题,属于被称为“NP完全”的难题一类。
给定一个写着数字的盘面,是否存在哪怕一种与这些数字不矛盾的地雷摆法。
平时玩的时候考虑的“这一格安全吗”这个问题,也与这个问题有着深刻的联系。
什么是NP完全
简单地说,NP完全是具有下面这些性质的问题。
- 检验答案对不对很容易:只要给你看一种地雷的摆法,就能马上检查它和所有数字是否吻合。
- 找出答案很难(据认为如此):盘面一大,摆法的候选数量就会急剧增加。目前已知的任何方法,都还没有找到对任何盘面都能很快得出答案的。
而且,已知NP完全问题之间可以互相转换。只要其中任何一个找到了对任何情况都能快速求解的办法,其他NP完全问题也就全都能快速求解。“有没有快速求解的办法”就是著名的未解难题“P≠NP猜想”,它是被悬赏100万美元的问题之一。
摆法的数量会迅速变得巨大
检查摆法之所以费劲,是因为候选的数量变得非常庞大。
- 在9×7的盘面上摆8个地雷,摆法数是从63格里选8格的组合数,约39亿种。
- 在26×15的盘面上摆75个地雷,摆法数是从390格里选75格的组合数,是一个超过80位的数。
当然,实际玩的时候没有必要全部检查。不与数字相邻的格子可以放在一起考虑,多数局面只看一两个数字就能确定。即便如此,在数字错综复杂地交织在一起的局面里,要确切地得出答案有时会很费劲。
应用只挑选人能靠推理解开的盘面
应用“扫雷”在生成盘面时,会确认能否只用人会用的下面3条规则,从头到尾解开。
- 从一个数字能知道的信息
- 组合两个数字能知道的信息
- 根据整个盘面剩余的地雷数能知道的信息
每条规则查看的范围都很小,可以很快检查。用这3条解不开的盘面,会移动地雷重新生成。因此玩的人也不必用检查全部摆法那样沉重的思路,一定能解到最后。
本站的文章中可以玩的盘面也是按同样的思路生成的。在电脑上测量生成与★5一样大小的盘面所需的时间,平均每个盘面只需几毫秒。
益智游戏与数学
数独等许多其他纸笔类益智游戏,在盘面放大的一般形式下,也已知是NP完全问题。能让人开心解开的益智游戏,很多都被设计成“不必全部检查,也能一步步推理解开”。应用“扫雷”的无需猜测的盘面,也是其中之一。
关于概率的计算,在扫雷的概率里有介绍。
