October 20, 2007
October 29, 2002

Mathematicians Prove Tetris Is Tough

By Sarah Graham

E-mail ArticleE-mail Print ViewPrint RSSRSS Stumble ItStumbleIt digg reddit newsvine

Science Image: Tetris screenshot
The video game Tetris is one of the most popular computer games ever created, perhaps in part because its difficulty makes it addictive. The objective of the game is to move and rotate falling geometric shapes to form complete rows at the bottom of the game board. Now scientists have shown mathematically that the problem posed by Tetris's descending tetrominoes is one of the most difficult to solve, even if you know which pieces are coming next.

Erik D. Demaine, Susan Hohenberger and David Liben-Nowell of the Massachusetts Institute of Technology determined that Tetris qualifies as an NP-complete problem. That is, although it's relatively easy to check whether a solution to the problem is valid, there is no efficient way to optimize any of the game's objectives. These include maximizing the number of rows cleared, maximizing the number of pieces placed successfully before losing, maximizing the number of "tetrises" (clearing four rows simultaneously) and keeping the height of the grid as low as possible over the course of a game. And in the simulated games the team studied, the player knew all of the upcoming pieces ahead of time--a situation that should have been more straightforward than the real thing, in which randomly selected pieces fall quickly from the top of the screen.

ADVERTISEMENT (article continues below)

The researchers further found that Tetris is an NP-hard problem, which means it is as least as difficult to solve as any other NP problem. "While you're playing Tetris, you're really solving hard problems," Demaine says. Interestingly, another seemingly simple but highly addictive game, Minesweeper, is also an NP-hard problem. So the next time you lose at either, take comfort in the fact that a computer may not have been able to do much better.

News Bytes of the Week—Watson in Disgrace Chimpanzees are manipulative liars, Blood test for Alzheimer's and more…:
Coal-Friendly Climate Changes in Kansas
Cave Speak: Did Neandertals Talk?
Wikipedia "Good Samaritans'' Are on the Money
Election fix? Switzerland Tests Quantum Cryptography
 Free Newsletters   

Special AD Section

Subscribe to Scientific American

Sciam.com Mobile Site

  Profile: Edmund D Pellegrino
  The policy outlook from the Hill
  HDAC inhibitors overcome first hurdle
  Upward trend in financing continues, but fewer feel flush
News from Scientific American Mind