# Mathematicians Prove Tetris Is Tough

Image: NINTENDO OF AMERICA

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.

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.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Scientific American Mind | 14 hours ago | 6

### Age Brings Happiness

• Information Culture | May 24, 2013

• TechMediaNetwork | May 24, 2013 | 10

### Why the Internet Sucks You in Like a Black Hole

• TechMediaNetwork | May 24, 2013 | 1

### Minor Lunar Eclipse Tonight: How to Watch It Online

• Overthinking It | May 24, 2013

More »

## Latest from SA Blog Network

• ### EXPOSED: The Global Epidemic of TB

PsiVid | 3 hours ago
• ### A Monkey with Human Eyes and Other Links from the Brink

Extinction Countdown | 13 hours ago
• ### Physics Week in Review: May 25, 2013

Cocktail Party Physics | 17 hours ago
• ### NeuroSCIence in FIction: Kill Decision

MIND
Illusion Chasers | 23 hours ago
• ### #SciAmBlogs Friday - Kirk vs. Spock, bridge failure, elephant seals, chemical intuition, predatory journals, sleep learning, and more.

STAFF
The Network Central | 23 hours ago

## Science Jobs of the Week

Mathematicians Prove Tetris Is Tough

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X

X

X