Interesting Esoterica

Tetris is Hard, Even to Approximate

Article by Demaine, Erik D and Hohenberger, Susan and Liben-Nowell, David
  • Published in 2008
  • Added on
In the collection
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 pieces 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.

Links

Other information

arxivId
arXiv:cs/0210020v1
journal
Technology
pages
1--56

BibTeX entry

@article{Demaine2008,
	title = {Tetris is Hard, Even to Approximate},
	author = {Demaine, Erik D and Hohenberger, Susan and Liben-Nowell, David},
	url = {http://arxiv.org/abs/cs/0210020 http://arxiv.org/pdf/cs/0210020v1},
	archivePrefix = {arXiv},
	arxivId = {arXiv:cs/0210020v1},
	eprint = {0210020v1},
	journal = {Technology},
	pages = {1--56},
	primaryClass = {arXiv:cs},
	year = 2008,
	urldate = {2011-11-23},
	abstract = {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 pieces 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.},
	collections = {Attention-grabbing titles}
}