Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell wrote a paper on the computational complexity of Tetris. 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 … Continue reading Tetris is Hard, Even to Approximate