Tetris
Computational complexity

In computer science, it is common to analyze the computational complexity of problems, including real-life problems and games. It was proven that for the "offline" version of Tetris (the player knows the complete sequence of pieces that will be dropped, i.e. there is no hidden information) the following objectives are NP-complete:

Also, it is difficult to even approximately solve the first, second, and fourth problem. It is NP-hard, given an initial gameboard and a sequence of p pieces, to approximate the first two problems to within a factor of p for any constant ε > 0.It is NP-hard to approximate the last problem within a factor of 2 − ε for any constant ε > 0.

To prove NP-completeness, it was shown that there is a polynomial reduction between the 3-partition problem, which is also NP-complete, and the Tetris problem.
detectable_content:number_placeholders[8]