在扫雷游戏中，你是否曾经感到困惑，不知道哪些格子安全，哪些格子可能藏有地雷?英国数学家 Richard Kaye 于 2000 年在《Mathematical Intelligencer》杂志上发表了一个研究1，表明扫雷游戏和一个数学概念“NP 完全问题”有着紧密联系。
什么是 NP 完全问题?
NP完全问题是一类看似简单，但求解起来非常困难的问题。什么叫“简单”呢?就是能够很快判断一个答案是否正确。什么叫“困难”呢?就是目前没有高效的算法可以求解。
举个例子，一个迷宫游戏，给你一个入口和出口，里面有很多岔路，让你判断“是否存在”一条从入口通到出口的路径。判断一个给你的路径是否可行很简单，但要你自己找到这样一条路径却很难。
NP完全问题就像这个迷宫游戏一样，验证答案简单，穷举求解困难。数学家们在研究如何求解这类问题，或者证明它们无法高效求解。
前面的例子已经直观解释了什么是 NP 完全问题，至于为什么叫“NP”?感兴趣的读者可以继续看下面这个解释。
像给定一条迷宫的路径，判断是否可行，这种答案是有“是”或“否”的“是非题”，称为决定性问题(decision problem)。而决定性问题有两大类，分别为P问题和NP问题。P问题是容易求解的问题，NP问题是容易判断某个答案是否正确，但是没有高效的算法可以正面求解的问题。更严谨地说，这里说的“容易”、“高效的算法”，指的是“在多项式时间内找出解”，因此， P 和 NP 的“P”就是多项式的英文 polynomial。NP 问题的全称是 nondeterminate polyomial(不确定多项式)。
如果能证明 P=NP，那么就可以证明NP问题也能高效求解，但是，NP 是否等于 P 是克雷数学研究所的七大千年数学难题之一。
扫雷是 NP 完全问题
扫雷游戏也属于 NP 完全问题。判断一个方块是否安全等价于构造一个 NP 完全问题的验证过程。这说明扫雷也是一类验证简单但求解困难的问题。更严谨的证明过程可以参考 Kaye 教授的论文1，另外也有一篇中文文章2做了证明。证明的思路基本上是把扫雷的一些盘面看作数字逻辑电路，为什么能看作是数字逻辑电路?可以参考果壳网的一篇文章3。
这就意味着扫雷游戏位于数学研究的前沿。Kaye 教授的研究揭示，扫雷这款大众游戏，其难度已经达到了数学研究的前沿。这说明解决 NP 完全问题具有深远的理论意义和实际应用价值。我们在游戏中也可以留意其中的数学结构，这有助于训练抽象思维能力。但是要解决 NP 问题还需要长期努力，距离找到通用高效算法仍然任重而道远。
扩展阅读
Kaye, Richard. "Minesweeper is NP-complete." Mathematical Intelligencer 22.2 (2000): 9-15.
