Complexitat del Tetris

Abstract

The computational complexity of Tetris has been studied across various problem formulations and game variations, most of which are classified as NP-hard. This paper explores the factors contributing to this complexity. We begin by generalizing the Tetris problem, parametrizing its components to create a unified definition for all variations. Next we examine existing research and identify findings about each variant. After the analysis, we focus on a specific variation of Tetris with dominoes, addressing the open problem of survival with rotation by demonstrating that it is solvable in polynomial time. Additionally, we present progress on other problems related to Tetris with dominoes.