Fitxers

TFG_Ros_Domenech_Pol.pdf (793.02 KB)

Tipus de document

Treball de fi de grau

Data de publicació

2025-06-10

Llicència de publicació

cc-by-nc-nd (c) Pol Ros Domènech, 2025
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/227713

Complexitat del Tetris

Títol de la revista

Autors

Director/Tutor

ISSN de la revista

Títol del volum

Recurs relacionat

Resum

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.

Descripció

Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Kolja Knauer i Carme Àlvarez Faura

Matèries

Complexitat computacional, Algorismes, Teoria de la computació, Videojocs, Treballs de fi de grau, Pol Ros Domènech

Matèries (anglès)

Computational complexity, Algorithms, Theory of computation, Video games, Bachelor's theses

Citació

Col·leccions

Treballs Finals de Grau (TFG) - Matemàtiques

Citació

ROS DOMÈNECH, Pol. Complexitat del Tetris. [consulted: 30 of May of 2026]. Available at: https://hdl.handle.net/2445/227713

Exportar metadades

JSON - METS

Compartir registre