# 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.

Rights & Permissions

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

• @ScientificAmerican | 9 hours ago

### Can We Harness Disruption to Improve Our World's Future?

• News | 10 hours ago

### Federal Flood Maps Left New York Unprepared for Sandy, and FEMA Knew It

• News | 12 hours ago

### Smart Wig Could Compete with Google Glass

• News | 13 hours ago | 1

### Will to Persevere Can Be Triggered by Electric Stimulation

• Climatewire | 14 hours ago | 6

More »

## Latest from SA Blog Network

• ### Wonderful Things: The Pugnacious, Alien-esque Skeleton Shrimp

The Artful Amoeba | 7 hours ago
• ### Can We Harness Disruption to Improve Our World's Future?

STAFF
@ScientificAmerican | 9 hours ago
• ### British Storm Brings Up History's First Work of Social Media

Plugged In | 10 hours ago
• ### Rolling on Wheels That Aren t Round

Observations | 10 hours ago
• ### The future of nuclear energy: Let a thousand flowers bloom

The Curious Wavefunction | 11 hours ago

## Science Jobs of the Week

Mathematicians Prove Tetris Is Tough

X

Give a 1 year subscription as low as \$14.99

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