扫雷是NP完全问题

zhiqiang6月 11, 2008 计算机科学

本科时有同学扫雷最快可以在60多秒完成高级难度，让我这种最快130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP完全的...

结果于2000年发表在Mathematical Intelligencer上，论文题目是Minesweeper is NP-complete，这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路，包括NP-hard的3SAT问题。作者还有一个非常直观的PPT演示证明过程，比如下图展示如何编码AND逻辑门： $t=u\wedge v$

它是NP完全问题说明如果程序要想完全正确，所费的时间最坏情况下将是指数的。不过我猜测对于大部分的扫雷的实例还是很容易的，而且NPC所用的规约实例特别大，所以编一个能较快速度解决大部分windows自带的那个高级难度的扫雷问题还是可行的，不知道是否已经有这方面的程序。

查看更多关于NP hard, 扫雷, 精华区的内容。

你可能感兴趣的

At 2008.06.11 22:52, Think said:

怎么知道的？上TCS课知道的？

[Reply]
- At 2008.06.11 23:11, zhiqiang said:
  
  不是的。我是在网上无意中看到的。
  
  [Reply]
  - At 2008.06.12 06:22, fdgh said:
    
    [Reply]
    - At 2008.06.13 04:51, nice said:
      
      Nice
      
      [Reply]
At 2008.06.11 23:21, wenyong said:

有点意思

[Reply]
At 2008.06.12 00:36, yoyo said:

我是50多秒……
不知道网上游戏时有的人会用挂一两秒内解决那是怎么实现的呢？

[Reply]
At 2008.06.12 04:46, loewez said:

这个证明思路挺有启发性的剑走偏锋
扫雷大概是世界上最多人参加解决的npc问题了吧

[Reply]
At 2008.06.12 08:42, amao said:

已经有这样的程序了。而且是很早之前就有了，所谓外挂。

[Reply]
At 2008.06.12 09:11, Moses said:

在启动扫雷的后, 按 xyzzy 再按 shift 后开始游戏, 这时鼠标指到格子上时, 观察屏幕的左上角会有一个针尖大小的亮点, 当亮点熄灭时表明该格子是地雷, 亮点亮时则不是地雷 (最好先把墙纸关掉, 桌面设为黑色).

[Reply]
- At 2008.06.13 12:05, IQ180 said:
  
  好像不行啊
  
  [Reply]
  - At 2008.06.13 14:24, zpnec said:
    
    你需要非常仔细的观察左上角，最好把你的背景调一调，就一个像素那么大
    
    [Reply]
- At 2008.07.21 10:35, teacherlau said:
  
  我看到了.
  
  [Reply]
At 2008.06.12 11:21, Eagle_Fantasy said:

怎么感觉NPC问题无处不在呢！

[Reply]
At 2008.06.12 19:41, DaiLiang said:

这个是不是就是节一个线性方程组？

[Reply]
- At 2008.06.12 19:47, zhiqiang said:
  
  是的。不过是求整数解，而整数规划也是NPC的。
  
  [Reply]
At 2008.06.14 12:07, fly2never said:

貌似有这种程序哦,我以前都试过.
但是往往接到一半就需要自己动手点几下

[Reply]
At 2009.01.22 13:17, hacker47 said:

这种从算法上就很复杂了，不过如果从内部数据结构下手（crack)，就很简单了。

[Reply]

« 有序矩阵的中位数算法

Windows游戏中的NP完全问题 »

扫雷是NP完全问题

查看更多关于NP hard, 扫雷, 精华区的内容。

17条留言 -> 跳到留言表格

阅微堂