上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌＂。他说对了，不光扫雷，Windows自带的游戏都是NP完全的。Windows自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。
空当接龙是NP完全问题
论文：Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intell...

本科时有同学扫雷最快可以在60多秒完成高级难度，让我这种最快130秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP完全的...
结果于2000年发表在Mathematical Intelligencer上，论文题目是Minesweeper is NP-complete，这里有作者的简单的问题和证明介绍。证明方法是证明扫雷问题可以编码任何逻辑电路，包括NP-hard的3SAT问题...

好久没有写我的理论计算机初步系列了，其实复杂性这一块，虽然平时经常遇到，但由于问题都过于本质和困难，想这方面问题的时间反而不多。Ko教授就跟我说也许NP verse P这个题并不难，只不过大家认为它很难，结果就没有多少人去做了，大家一遇到这个问题都远远得绕开。话虽如此，我还是不敢去碰的。
很多人一看到NP-hard，就从字面上理解成为比NP还难的问题。但...