Erik Demaine, a 23-year old
professor working at
MIT's
CSAIL in
Cambridge, Massachusetts, has co-authored a paper proving the difficulty of
algorithmically solving a
Tetris game.
From the abstract of the paper:
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.
In other words, Tetris falls in the same class of tantalizing problems as the famous Traveling Salesman Problem or the Halting Problem. Demaine claims that it is the intellectual challenge of coming up with heuristics to crack the game that make it so addictive.
Source: "Tetris is Hard, Even to Approximate"; MIT-LCS-TR-865 Technical Report (2002)