扫雷是NP完全问题

作者:

本科时有同学扫雷最快可以在 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.

类似文章:
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本 On the graph isomorphism problem
Xie Xie 给我看了一个链接 性能调优--永远超乎想象 ,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
上篇文章 扫雷是 NP 完全问题 之后, You Xu 提到"不光扫雷是 NP 完全问题, 空当接龙 问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。
给定 \( n\times n\) 的实数矩阵,每行和每列都是递增的,求这 \( n^2\) 个数的中位数。
上篇文章 扫雷是 NP 完全问题 之后, You Xu 提到"不光扫雷是 NP 完全问题, 空当接龙 问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。