Tetris is a video and computer game, invented in 1985 by the Russian Alexey Pajitnov, that has become one of the most widely played games of all time. In 2002, computer scientists Erik Demaine, Susan Hohenberger and David Liben-Nowell of the Massachusetts Institute of Technology (MIT) analyzed the game to determine its computational complexity and found it to be an NP-hard problem (one that is immune to simple solution and instead demands exhaustive analysis to work out the best way to be completed).

Many people first played Tetris on the Nintendo Gameboy handheld console but it has since become available for virtually every personal computer-based device. The game gives the player the task of creating complete lines a series of regularly-shaped blocks – tetrominos, which are a type of polyomino – that advance steadily down a narrow grid. The blocks can be spun to make them fit together better and complete lines. The game gets faster as levels are completed, making it harder to spin and fit blocks together fast enough to form lines. The MIT team found that, subject to certain conditions, Tetris has much in common with some of the knottiest mathematical conundrums, including the traveling salesman problem. Because Tetris is NP-hard, there is no easy way to maximize a score at the game, even when the sequence of blocks is known in advance.