テトリスはNP-complete

• http://www.arxiv.org/abs/cs.CC/0210020

研究関係で調べものしてて偶然見つけたもの。テトリスの何がNPやねんとか思うわけだが、

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.

ということらしい。やっぱりなんだかよくわからんな。そのうち気が向いたら論文の中身も読んでみよう。