BBC NEWS Americas Africa Europe Middle East South Asia Asia Pacific
BBCi NEWS   SPORT   WEATHER   WORLD SERVICE   A-Z INDEX     

BBC News World Edition
 You are in: Technology  
News Front Page
Africa
Americas
Asia-Pacific
Europe
Middle East
South Asia
UK
Business
Entertainment
Science/Nature
Technology
Health
-------------
Talking Point
-------------
Country Profiles
In Depth
-------------
Programmes
-------------
BBC Sport
BBC Weather
SERVICES
-------------
EDITIONS
Saturday, 26 October, 2002, 08:46 GMT 09:46 UK
The trouble with Tetris
Tetris screenshot, THQ
Tetris: very tricky
Everyone knows that Tetris is compulsively playable, but now scientists have proved that it is harder than you think to complete.

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.

See also:

19 Apr 00 | Science/Nature
25 Dec 01 | Science/Nature
11 Jul 00 | Science/Nature
13 Jun 02 | Science/Nature
09 Sep 02 | dot life
20 May 02 | Science/Nature
Internet links:


The BBC is not responsible for the content of external internet sites

Links to more Technology stories are at the foot of the page.


E-mail this story to a friend

Links to more Technology stories

© BBC ^^ Back to top

News Front Page | Africa | Americas | Asia-Pacific | Europe | Middle East |
South Asia | UK | Business | Entertainment | Science/Nature |
Technology | Health | Talking Point | Country Profiles | In Depth |
Programmes