作者：zhiqiang 来源：阅微堂 酷勤网收集 2008-06-15
摘要
不光扫雷，Windows自带的游戏都是NP完全的。Windows自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。
上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌＂。他说对了，不光扫雷，Windows自带的游戏都是NP完全的。Windows自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。
空当接龙是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
顺便提一下蜘蛛纸牌的可以获胜的概率高达82-91.5%。而我平时自己玩的时候20%都不到。差距啊。