Tetris is Hard, Even to Approximate

Erik D. Demaine, Susan Hohenberger, David Liben-Nowell

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 configurati…