Tetris is hard, even to approximate
Tetris is hard, even to approximate
复制标题
DOI：
10.1142/s0218195904001354
复制
发表时间：
2004-04-01
影响因子：
--
通讯作者：
Liben-Nowell, D
中科院分区：
文献类型：
--
作者：
Breukelaar, R;Demaine, ED;Liben-Nowell, D
在流行的电脑游戏《俄罗斯方块》中，玩家将获得一系列方块，并必须将其打包到一个矩形游戏棋盘中；游戏棋盘上任何完全填满的行都会被清除，其上所有填满的方块都会下降一行。我们证明了在离线版本的俄罗斯方块中，最大化清除行数，最大化方块数（同时填充和清除的行数的四倍），最小化被占用方块的最大高度，或最大化游戏结束前放置的棋子数量是np完全的。我们进一步表明，当给定p个片段的序列时，这些目标的第一个和最后一个在p（1-epsilon）因子内的极端不逼近性，以及第三个目标在2 -epsilon因子内的不逼近性，对于任何epsilon > 0。我们的研究结果适用于《俄罗斯方块》规则的几种变体，包括不同的旋转模式、对玩家敏捷性的限制和受限的棋子设置。
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all filled squares above it drop by one row. We prove that in the offline version of Tetris, it is NP-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p(1-epsilon), when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of 2 - epsilon, for any epsilon > 0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.