曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。
首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的这篇文章。
上图就是一条带有Boolean值的线路。注意到x和x’中有且仅有一个有雷。如果（沿线路方向）前一个格子有雷，我们就说这条线路状态为True；反之如果后一个格子有雷，那么这条线路所传递的Boolean值就是False。每条线路的起始端都如下图左所示，其中符号*表示该格里必然有雷，x和x’中同样是有且仅有一个有雷，但到底是哪一个里面有雷谁也说不清楚。线路是可以拐弯的，如下图右所示，这可以保证转角后Boolean值相同。
我们需要构造一些特殊的扫雷布局来解释NOT门、AND门和OR门。构造NOT门最为简单，下图就是一个NOT门，注意经过了中间的NOT门后，x和x’的位置互换，True变成了False，False也将变成True。
AND门和OR门的构造就比较复杂了。下面是AND门的构造，U和V是输入的两条线路，T是输出的线路。为了说明这确实是一个AND门，我们将说明：在下面的构造中，如果线路T是True（即最右边那个格子t有雷）的话，那么格子u和v必须都有雷才行。如果最右边的格子t有雷，我们可以很快推断出，图中所有其它的t格都是有雷的，所有t’都是无雷的。观察a3正上方的那个”3″，我们立即看出a2,a3都必须有雷，于是继续推得a1无雷，s有雷。类似地，我们可以知道r也是有雷的。在中间一行的*4t处，4的上下左右都已经有雷了，那么u’和v’必然无雷，于是继续往左推得u和v都有雷。
OR门的构造比较类似，如下图。如果r无雷的话，可知a2,a3有雷，a1无雷，s’有雷，进而s无雷。观察”6″可知u’和v’都有雷，于是u和v均无雷。
不断套用这几个逻辑门的构造图来连接电路，直到输出线路只剩下唯一的一条。把最后的输出线路从x或者x’处截断（相当于把最终输出的Boolean值定下来）后，整个布局就成了一个“扫雷版SAT问题”了。
最后还有一个容易忽略的问题：要是线路交叉了该咋办？下图的构造可以保证线路交叉后仍不改变原线路所带的Boolean值。至此，我们已经可以把任一逻辑电路布局到扫雷棋盘上，解决这个扫雷问题就相当于要解一个逻辑电路问题，因此扫雷问题至少和逻辑电路问题一样难。
沙发…
很早以前就知道这个结论了～
呃，什么是扫雷问题呢？
从文中来看，扫雷问题似乎是“给定一个地图的初始状态，求满足这个初始状态的一个解”？
以前我还打算过编一个自动解扫雷的程序，没想到竟然是NPC
在http://zhiqiang.org/blog/上见过
我们需要把一个已知的NP完全问题规约到扫雷问题上去。
“规约”是不是应该是“归约”
PS:麻烦Matrix67牛再指点我DROD LV12关，我在和一个分身破蓝色怪物时卡住了，就是你要左边走一下，右边走一下，我先第一次向右走时卡住了……
回复：谢谢指正，已经改了
你说的是1E房间？把怪物引到箭头上，分身就踩不进去了
好……好……好简单的证明-.-~~~
太……强了，我完全拜倒在您的智慧之下了……
编写自动扫雷的软件可以先读取软件的数据,然后再用软件控制扫雷,不用自己求雷的位置.
楼层: 地幔 | 2008-7-06 22:42 | 阿健 说：
编写自动扫雷的软件可以先读取软件的数据,然后再用软件控制扫雷,不用自己求雷的位置.
=========================================
喂喂喂我们在讨论算法算法～不是这种技巧～
厉害
不错。不过有一点，这里minesweeper实际上是由planar-3-sat而不是一般的3-sat归约过去的。由这个问题建立归约也是证明平面几何问题np-completeness的常用思路。
“下图的构造可以保证线路交叉后仍不改变原线路所带的Boolean值”
没看到这句，是我想当然了。
Ｈ图的判定问题是ＮＰ完全的，即如果能有一个多项式时间算法，能判定任意一个给定图是否存在ＨＡＭＩＬＴＯＮ圈，即证明了ＮＰ＝Ｐ。
我为Ｈ图的判定找到了一个多项式时间算法，请看我的论文（Ａ Ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ａｌｇｏｒｉｓｍ ｆｏｒ ｊｕｄｇｉｎｇ Ｈ ｇｒａｐｈ）放在www.qiji.cn/eprint/abs/3747.html 上。诚恳地欢迎批评指正。
我依据此算法编制了两个程序，一个是为了演示，即对任意给定的图显示找到他的一个Ｈ圈的全过程。另一个是一个实用程序。欢迎有此需要的朋友与我联系。我知道在密码的编制，和解密上，和一些游戏软件上会用得上。
我深知我做了件非常有用的工作，但我年事已高，没有精力去完成它的复杂的推广工作，我诚心渴望有识之士能给我帮助，或合作。
我的ＥＭＡＩＬ：ＸＴＥＴＡＩ１＠ＳＩＮＡ．ＣＯＭ．ＣＮ
winmine 是可以在多项式时间内归约成 P 问题的。
大家打开 winmine, 然后输入 xyzzy, 再输入一次（或者奇数次） shift 键，观察屏幕左上角。将鼠标在地图上遍历，鼠标悬停的地方，若有雷则左上角像素点为黑色；若没有雷则为白色。可以证明这个过程的复杂度是 O(mn), 其中 m, n 分别是地图宽和高。
（恶搞一下……不要砸我……）
多谢，好东西，看了
NP是什么东西哦？
我用迷宫做出来了个
这个题目和“自动扫雷程序”是不一样。
这个题目并不是要“扫雷”，而是要生成一个图供玩家“扫”。
这个和“扫”雷完全不同，只是扫的话简单多了。自动扫雷程序是完全可以编出来的。
一般扫雷的地图是先设置雷的位置，然后再根据位置来填写参数。这个事情如果倒过来，先设置好参数，然后再来“布”雷，这真的太难了。
我花了很大功夫验算完“线路交叉”的那张图，感觉快要吐了
学习一下.
自动扫雷一般都是读内存的，谈不上什么有价值的算法
你说的那种是向扫雷程序注入一个钩子，然后去读取内存，然后从内存中把雷找到。
偶然发现你的这个BLOG。很喜欢上面的东西。
这个构造好强悍的说……
看了你的博客，很受启发，最近接到一个作业，是很诡异的扫雷。。。。能帮忙看一下么？我的邮箱是annjouno@gmail.com
看了，很好的说
我2003年写过一个扫雷算法，貌似时间复杂度是P的。一定是错了么？
这样多项式时间在扫雷里比作什么
复杂度比作什么
更多的NP问题簇等于什么
你这样计算之后得到的NP完全问题的解，即多项式时间复杂度的最优解公理的通用范围在哪里？
如果你开局就点到雷，难道这个最优解公理要赌第一步没有雷的情况下才可以继续解！
如果最顶尖的扫雷高手都可以写一个最优解公理？
多项式时间是NP的主旋律，不是你解题这个行为的多项式时间。
扫雷只有稳定因数复杂度，没有多项式时间，没有不稳定因数。更没有NP关联。
还有就是我对这个扫雷说无言以对……