OH, THE HOURS WASTED...:

The trouble with Tetris (BBC, 26 October, 2002)

Anyone who has played computer games over the last 15 years is likely to have encountered Tetris in one form or another. Many people first played it on the Nintendo Gameboy handheld console. [...]

Now Erik Demaine, Susan Hohenberger and David Liben-Nowell from the Laboratory of Computer Science at the Massachusetts Institute of Technology have analysed the game to determine its computational complexity.

The trio discovered that, subject to certain conditions, Tetris has much in common with some of the knottiest mathematical conundrums such as the Travelling Salesman Problem. [...]

The researchers found that Tetris was an NP-Hard problem, i.e. there was no easy way to maximise a score at the game, even when the sequence of blocks was known in advance.

We could have told them it was hard. Posted by Orrin Judd at October 26, 2002 12:41 PM