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 (in which all the pieces are known in advance) the following objectives are NP-complete:
Maximizing the number of rows cleared while playing the given piece sequence.
Maximizing the number of pieces placed before a loss occurs.
Maximizing the number of simultaneous clearing of four rows.
Minimizing the height of the highest filled grid square over the course of the sequence.
Also, it is not possible to find a polynomial time approximation algorithm for the first 2 problems and it is hard to approximate the last problem within 2 - n for every n > 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.
Maximizing the number of rows cleared while playing the given piece sequence.
Maximizing the number of pieces placed before a loss occurs.
Maximizing the number of simultaneous clearing of four rows.
Minimizing the height of the highest filled grid square over the course of the sequence.
Also, it is not possible to find a polynomial time approximation algorithm for the first 2 problems and it is hard to approximate the last problem within 2 - n for every n > 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.
