按年被提到
20022019 · 2 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:cs/0210020 · cs.CC

Tetris is Hard, Even to Approximate

俄罗斯方块很难,连近似也很难
Erik D. Demaine, Susan Hohenberger, David Liben-Nowell · 2002

证明离线俄罗斯方块的多种优化目标是 NP 完全且极难近似

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2007-11-16 · 最近 2019-09-04发表于 Lecture notes in computer science
6不同的人
6活跃月份
6讨论串
107被引(OpenAlex)

在已知方块序列的离线版俄罗斯方块中,证明最大化消行数、最大化四行同消次数、最小化最大高度、最大化放置方块数这几个目标都是 NP 完全。进一步证明第一个和最后一个目标难以在 p^(1-ε) 因子内近似(p 为方块数),第三个目标难以在 (2-ε) 因子内近似。结论在多种规则变体下仍然成立。

HN 为什么提它

评论者把它当作俄罗斯方块是 NP 完全的出处,提到证明用到数字划分的归约,也有人提醒这类结果针对的是广义版本。

其他难度 3 / 5约 35 分钟经得起时间
读之前最好知道
1NP 完全性(NP-completeness)
2多项式时间归约(reduction)
3近似算法与不可近似性
4划分问题(partition)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐dangrover · 2008-12

“kind of an interesting proof -- they reduce it to the problem of partitioning multisets of numbers into groups of equal sums”

觉得证明有趣:把问题归约为把数的多重集划分成和相等的组
Tetris Challenge原评论 ↗
引用Xk · 2011-07

“For those that care, a few years ago some researchers proved Tetris is NP-complete for many problems.”

补充几年前有研究者证明俄罗斯方块在很多情形下是 NP-complete
Solving Tetris in C原评论 ↗
引用croikle · 2013-05

“Note that results like this [0] tend to be for generalizations.”

提醒这类结果往往针对推广后的版本
Calculating the perfect Tetris play: Part I原评论 ↗
引用bjourne · 2019-09

“It also has been shown that such a setup makes the game NP complete. Tetris is Hard, Even to Approximate”

引用它说明这样的设定使游戏成为 NP-complete
A history of Tetris randomizers (2018)原评论 ↗
被提交为 story · 2 次