In the popular computer game of \emph{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-\varepsilon}$, when given a sequence of $p$ pieces, and the
inapproximability of the third objective to within a factor of $2 -
\varepsilon$, for any $\varepsilon >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.