Image: NINTENDO OF AMERICA

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.