Windows自带的游戏都是NP完全问题
先说说扫雷，曾经见识过有人神人可以在60多秒完成高级难度，让我这种最快才130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直没机会写。现在才知道，原来扫雷问题是NP完全的…
结果于2000年发表在Mathematical Intelligencer上，论文题目是Minesweeper is NP-complete，这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路，包括NP-hard的3SAT问题。作者还有一个非常直观的PPT演示证明过程。
它是NP完全问题说明如果程序要想完全正确，所费的时间最坏情况下将是指数的。不过我猜测对于大部分的扫雷的实例还是很容易的，而且NPC所用的规约实例特别大，所以编一个能较快速度解决大部分windows自带的那个高级难度的扫雷问题还是可行的，不知道是否已经有这方面的程序。
不光扫雷，Windows自带的游戏空当接龙和蜘蛛纸牌都是NP完全的。
空当接龙是NP完全问题
论文：Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
蜘蛛纸牌是NP完全问题
论文：Springer Berlin, Heidelberg, The Complexity of Solitaire, Mathematical Foundations of Computer Science 2007: 182-193, 2007
PS：蜘蛛纸牌的可以获胜的概率高达82-91.5%。而我平时自己玩的时候20%都不到。这就是差距啊。