1
扫雷是 NP 完全问题
source link: https://zhiqiang.org/cs/minesweeper-is-np-complete.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
扫雷是 NP 完全问题
本科时有同学扫雷最快可以在 60 多秒完成高级难度，让我这种最快 130 秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP 完全的...
结果于 2000 年发表在Mathematical Intelligencer上，论文题目是 Minesweeper is NP-complete ，这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路，包括 NP-hard 的 3SAT 问题。作者还有一个非常直观的 PPT演示证明过程，比如下图展示如何编码 AND 逻辑门：t=u∧vt=u∧v
它是 NP 完全问题说明如果程序要想完全正确，所费的时间最坏情况下将是指数的。不过我猜测对于大部分的扫雷的实例还是很容易的，而且 NPC 所用的规约实例特别大，所以编一个能较快速度解决大部分 windows 自带的那个高级难度的扫雷问题还是可行的，不知道是否已经有这方面的程序。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK