关于支持科学新闻业
如果您喜欢这篇文章，请考虑通过支持我们屡获殊荣的新闻业 订阅。通过购买订阅，您正在帮助确保关于塑造我们今天世界的发现和想法的有影响力的故事的未来。
视频游戏俄罗斯方块是有史以来最受欢迎的电脑游戏之一，也许部分原因是它的难度使其令人上瘾。游戏的目标是移动和旋转下落的几何形状，以在游戏板底部形成完整的行。现在科学家们已经用数学方法证明，由俄罗斯方块的下落四格骨牌提出的问题是最难解决的问题之一，即使你知道接下来会出现哪些方块。
马萨诸塞理工学院的 Erik D. Demaine、Susan Hohenberger 和 David Liben-Nowell 确定俄罗斯方块符合 NP 完全问题的条件。也就是说，虽然检查问题的一个解决方案是否有效相对容易，但是没有有效的方法来优化游戏的任何目标。这些目标包括最大化消除的行数，最大化在失败前成功放置的方块数，最大化“俄罗斯方块”（同时消除四行）的数量，以及在整个游戏过程中尽可能保持网格的高度较低。而且在研究小组研究的模拟游戏中，玩家提前知道所有即将到来的方块——这种情况应该比真实情况更简单，在真实情况中，随机选择的方块会从屏幕顶部快速落下。
研究人员进一步发现俄罗斯方块是一个 NP 难问题，这意味着它至少与任何其他 NP 问题一样难以解决。“当你在玩俄罗斯方块时，你实际上是在解决难题，”Demaine 说。有趣的是，另一个看似简单但高度令人上瘾的游戏扫雷也是一个 NP 难问题。所以下次你在这两个游戏中失败时，可以安慰自己，计算机可能也做得不会好多少。