The trouble with Tetris

The game was invented in 1985 by Russian Alexey Pajitnov and has since become one of the most widely played games of all time.

Now US computer scientists have analysed it and found it has a lot in common with the hardest problems in mathematics.

These problems are immune to simple solutions and instead demand exhaustive analysis to work out the best way to complete them.

Knotty blocks

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.

The game gives the player the task of creating complete lines with the regularly-shaped series of blocks 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.

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.

No quick fix

This problem involves working out the most efficient route for a salesman or delivery man who has to visit lots of different locations.

These types of problems, known as NP-Hard problems, are difficult because there is no shortcut or smart algorithm that will solve them swiftly.

Instead, all possible solutions have to be tried to find out which produces the best result.

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.