扫雷是 NP 完全问题

作者: , 共 437 字 , 共阅读 0

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

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

扫雷的AND逻辑门

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

Q. E. D.

类似文章：
相似度: 0.302
碎碎念 » 扫雷
昨天刚加入了扫雷网：http://saolei.wang/Player/Index.asp?Id=24185。
相似度: 0.232
计算机科学 » 算法复杂度, 空当接龙, 蜘蛛纸牌
上篇文章扫雷是 NP 完全问题之后，You Xu提到＂不光扫雷是 NP 完全问题，空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌＂。他说对了，不光扫雷， Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。
相似度: 0.184
计算机科学 » 数据库, 算法复杂度
问题来自美人他爹和Wangjianshuo's blog
相似度: 0.171
计算机科学 » NP hard, NP vs P, NP complete, 算法复杂度
很多人一看到 NP-hard ，就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话，这个论断是不正确的。从算法角度来看， NP-hard 问题的确比 NP 难，但比 NP 还难（指花费时间更多）的问题却不见得是 NP-hard 的。
相似度: 0.113
计算机科学 » 图同构, 算法复杂度
更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。
相似度: 0.085
计算机科学 » NP, NP Complete, P vs NP, 理论计算机初步
P = NP?
相似度: 0.084
计算机科学 » 博弈论, 算法复杂度
Game Theory 即博弈论，目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年，理论计算机界对它的研究也很热。
相似度: 0.065
计算机科学 » 算法复杂度, 算法, 素数
Xie Xie 给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。
相似度: 0.061
计算机科学 » P vs NP, 理论计算机初步
上篇文章已经提到， P vs NP 是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中， NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。
相似度: 0.058
编程 » Python, numpy
今天写 Python 代码时遇到一个恶心的 bug ，花了好一会才定位和搞清楚。我的目标是寻找第一个非 NAN 的数的位置（其中 array 是一个 numpy 向量），很自然有下面实现：
前一篇：
计算机科学 » 中位数, 算法
给定$ n\times n$ 的实数矩阵，每行和每列都是递增的，求这$ n^2$ 个数的中位数。
后一篇：
计算机科学 » 算法复杂度, 空当接龙, 蜘蛛纸牌
上篇文章扫雷是 NP 完全问题之后，You Xu提到＂不光扫雷是 NP 完全问题，空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌＂。他说对了，不光扫雷， Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。