您可以在百度里搜索“数学之书：数学史上250个里程碑式的发现 艾草文学(www.321553.xyz)”查找最新章节！

　　※246.NP完备的俄罗斯方块

　　德曼恩（Erik D.Demaine，1981—）乌恩别格（Susan Hohenberger，1978—）利宾诺威（David Liben-Nowell，1977—）

　　2002年

　　计算机科学家在2002年量化俄罗斯方块的困难度，证明它的困难度和数学领域中最难的问题不相上下，不但没有简单解答这一回事，还需要费时、费力的分析才能找到最佳化的答案。

　　圈叉游戏（约公元前1300年），围棋（公元前548年），永恒难题（1999年），破解艾瓦里游戏（2002年）及破解西洋跳棋（2007年）

　　1985年由俄罗斯计算机工程师帕基特诺夫（Alexey Pajitnov）所发明的俄罗斯方块是非常受欢迎的积木堆叠游戏。美国计算机科学家在2002年量化俄罗斯方块的困难度，证明它的困难度和数学领域中最难的问题不相上下，不但没有简单解答这一回事，还需要费时、费力的分析，才能找到最佳化的答案。

　　俄罗斯方块一开始在屏幕上方会有积木般的物品往下掉，在积木下降的过程中，玩家可以旋转积木并令积木朝屏幕两端移动。这些积木的造型称之为四格骨牌，顾名思义，就是由四个正方形彼此相连成一个群，看起来就像字母“T”或是其他简单的形状。当一块积木触及屏幕底层的时候会被固定住，然后会有另一块积木再次从天而降。当屏幕下方任一列整个被积木补满时会自动消失，其上较高位置的每一列会因此下降一列。当新的积木完全被堵住、没地方可以下降时，这个游戏也就终止了，所以，玩家的目标就是尽可能延长游戏时间，设法累积更多的分数。

　　德曼恩、乌恩别格和利宾诺威三位研究人员在2002年找出俄罗斯方块游戏一般化的版本，适用于各种宽度、高度的矩形游戏范围。这三人研究团队还证明在给定积木出现顺序的条件下，尽可能清除最多列的方法，是一个NP完备问题（NP-complete，NP两个字分别代表Nondeterministically和Polynomial，即无法判定的多项式）。虽然这一类问题的答案还是可以验证对错与否，但是，花在找答案的时间就足以让人闻之色变了。NP完备问题的经典范例是业务员旅程问题，要在其中找出能让业务员以最佳效率完成旅程的方式，或者是安排旅人前往许多一定要造访的城市，都是非常具有挑战性的工作，困难之处就在于既没有快捷方式，也没有高明的算法可以很快地找到答案。 数学之书：数学史上250个里程碑式的发现