We analyze the problem of packing squares in an online fashion: Given a semi-infinite strip of width 1 and an unknown sequence of squares of side length in [0,1] that arrive from above, one at a time. The objective is to pack these items as they arrive, minimizing the resulting height. Just like in the classical game of Tetris, each square must be moved along a collision-free path to its final destination. In addition, we account for gravity in both motion (squares must never move up) and position (any final destination must be supported from below). A similar problem has been considered before; the best previous result is by Azar and Epstein, who gave a 4-competitive algorithm in a setting without gravity (i.e., with the possibility of letting squares "hang in the air") based on ideas of shelf-packing: Squares are assigned to different horizontal levels, allowing an analysis that is reminiscent of some bin-packing arguments. We apply a geometric analysis to establish a competitive factor of 3.5 for the bottom-left heuristic and present a 34 13=2.615...-competitive algorithm.
Tetris Every reader is certainly familiar with the classical game of Tetris: Given a strip of fixed width, find an online placement for a sequence of objects falling down from above such that space is utilized as good as possible. In comparison to the strip packing problem, there is a slight difference in the objective function as Tetris aims at filling rows. In actual optimization scenarios this is less interesting as it is not critical whether a row is used to precisely 100 full rows do not magically disappear in real life. In this process, no item can ever move upward, no collisions between objects must occur, an item will come to a stop if and only if it is supported from below, and each placement has to be fixed before the next item arrives. Even when disregarding the difficulty of ever-increasing speed, Tetris is notoriously difficult: Breukelaar @cite_11 show that Tetris is -hard, even for the, original, limited set of different objects.
@cite_11
2146302034
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all filled squares above it drop by one row. We prove that in the offline version of Tetris, it is -complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p1-e, when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of 2-e, for any e>0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.