经典证明:扫雷是NP完全问题

    曾经看到过自动扫雷软件,当时我就在想,扫雷游戏是否有什么牛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值。至此,我们已经可以把任一逻辑电路布局到扫雷棋盘上,解决这个扫雷问题就相当于要解一个逻辑电路问题,因此扫雷问题至少和逻辑电路问题一样难。
   

26 条评论

  • hetong_007

    沙发…
    很早以前就知道这个结论了~

  • karl6833

    呃,什么是扫雷问题呢?
    从文中来看,扫雷问题似乎是“给定一个地图的初始状态,求满足这个初始状态的一个解”?

  • CmYkRgB123

    以前我还打算过编一个自动解扫雷的程序,没想到竟然是NPC

  • qcthreestones

    在http://zhiqiang.org/blog/上见过

  • Freeze

    我们需要把一个已知的NP完全问题规约到扫雷问题上去。
    “规约”是不是应该是“归约”
    PS:麻烦Matrix67牛再指点我DROD LV12关,我在和一个分身破蓝色怪物时卡住了,就是你要左边走一下,右边走一下,我先第一次向右走时卡住了……

    回复:谢谢指正,已经改了
    你说的是1E房间?把怪物引到箭头上,分身就踩不进去了

  • Satily

    好……好……好简单的证明-.-~~~

  • Freeze

    太……强了,我完全拜倒在您的智慧之下了……

  • 阿健

    编写自动扫雷的软件可以先读取软件的数据,然后再用软件控制扫雷,不用自己求雷的位置.

  • NOVA

    楼层: 地幔 | 2008-7-06 22:42 | 阿健 说:

    编写自动扫雷的软件可以先读取软件的数据,然后再用软件控制扫雷,不用自己求雷的位置.
    =========================================
    喂喂喂我们在讨论算法算法~不是这种技巧~

  • foo

    不错。不过有一点,这里minesweeper实际上是由planar-3-sat而不是一般的3-sat归约过去的。由这个问题建立归约也是证明平面几何问题np-completeness的常用思路。

  • foo

    “下图的构造可以保证线路交叉后仍不改变原线路所带的Boolean值”

    没看到这句,是我想当然了。

  • xyingtai

    H图的判定问题是NP完全的,即如果能有一个多项式时间算法,能判定任意一个给定图是否存在HAMILTON圈,即证明了NP=P。
    我为H图的判定找到了一个多项式时间算法,请看我的论文(A Polynomial time algorism for judging H graph)放在www.qiji.cn/eprint/abs/3747.html 上。诚恳地欢迎批评指正。
    我依据此算法编制了两个程序,一个是为了演示,即对任意给定的图显示找到他的一个H圈的全过程。另一个是一个实用程序。欢迎有此需要的朋友与我联系。我知道在密码的编制,和解密上,和一些游戏软件上会用得上。
    我深知我做了件非常有用的工作,但我年事已高,没有精力去完成它的复杂的推广工作,我诚心渴望有识之士能给我帮助,或合作。
      我的EMAIL:XTETAI1@SINA.COM.CN

  • Excessuz

    winmine 是可以在多项式时间内归约成 P 问题的。
    大家打开 winmine, 然后输入 xyzzy, 再输入一次(或者奇数次) shift 键,观察屏幕左上角。将鼠标在地图上遍历,鼠标悬停的地方,若有雷则左上角像素点为黑色;若没有雷则为白色。可以证明这个过程的复杂度是 O(mn), 其中 m, n 分别是地图宽和高。
    (恶搞一下……不要砸我……)

  • 张若寒

    多谢,好东西,看了

  • 123

    NP是什么东西哦?

    我用迷宫做出来了个

  • thiswind

    这个题目和“自动扫雷程序”是不一样。

    这个题目并不是要“扫雷”,而是要生成一个图供玩家“扫”。

    这个和“扫”雷完全不同,只是扫的话简单多了。自动扫雷程序是完全可以编出来的。

    一般扫雷的地图是先设置雷的位置,然后再根据位置来填写参数。这个事情如果倒过来,先设置好参数,然后再来“布”雷,这真的太难了。

    我花了很大功夫验算完“线路交叉”的那张图,感觉快要吐了

  • takuma888

    学习一下.

  • Bili

    自动扫雷一般都是读内存的,谈不上什么有价值的算法

  • 人从众

    偶然发现你的这个BLOG。很喜欢上面的东西。

  • 九歌_东皇

    这个构造好强悍的说……

  • pop

    看了你的博客,很受启发,最近接到一个作业,是很诡异的扫雷。。。。能帮忙看一下么?我的邮箱是annjouno@gmail.com

  • cervelo

    看了,很好的说

  • c'c'c'c

    我2003年写过一个扫雷算法,貌似时间复杂度是P的。一定是错了么?

  • 文夏

    这样多项式时间在扫雷里比作什么
    复杂度比作什么
    更多的NP问题簇等于什么
    你这样计算之后得到的NP完全问题的解,即多项式时间复杂度的最优解公理的通用范围在哪里?
    如果你开局就点到雷,难道这个最优解公理要赌第一步没有雷的情况下才可以继续解!
    如果最顶尖的扫雷高手都可以写一个最优解公理?
    多项式时间是NP的主旋律,不是你解题这个行为的多项式时间。
    扫雷只有稳定因数复杂度,没有多项式时间,没有不稳定因数。更没有NP关联。
    还有就是我对这个扫雷说无言以对……

发表评论

9  ×  1  =