Treffer: Tetris-Packing Problem With Maximizing Filled Grid Squares

Tetris is a classic video game invented by Alexey Pazhitnov, a Russian mathematician, in the 1980’s. A player starts out with an empty vertical game board divided into unit squares. The game pieces consist of an endless random sequence of tetrominoes, or shapes made up of four unit squares arranged in various ways. As each piece falls, players must slide them left or right or rotate them, in order to form complete rows of unit blocks. Completed rows of unit grid squares are eliminated from the stack and a new empty row is created on top. The game ends when the height of the block stack prevents placing new pieces. Scoring is based on the number of rows eliminated. Breukelaar, et al. [3] recently formalized the game into the Tetris Problem, which they proved NP-hard. Their version allowed for game boards of arbitrary initial configuration, width, and height. We present a new class of packing problems called the Tetris-Packing Problem (TPP). A problem instance is a 5-tuple G = (β, (w, h), (P1, P2, … , Pp), {S1, S2, … , Ss}, u) where β is the initial configuration of the game board (empty or arbitrary), (w, h) specifies the dimensions of the game board, (P1, P2, … , Pp) is a sequence of p game pieces each belonging to the shape set {S1, S2, … , Ss}, and u specifies if the top of the board is open or closed (whether pieces can be extended partially beyond its top). Unlike the game of Tetris, TPP has no line elimination. We prove that TPP is generally NP-hard with the objective function of number of filled grid squares. We describe T-PACK, a Java API for implementing and testing Tetris-Packing heuristics, with which we developed the Corner Fit, Deepest Fit, Hybrid Corner/Deepest Fit, and Modified Best Fit heuristics.