2

The game of Tetris is played on a grid of squares that is 10 squares across and 20 squares high. Over the course of the game, tetrominoes (geometric shapes consisting of four squares connected orthogonally) fall from above and lock into place whenever the tetromino makes contact with either the bottom of the grid or the top of another tetromino.

Since rotation is allowed in Tetris, there are 7 total tetrominoes that exist and each can be assigned a specific color or symbol to represent squares on the grid that belong to a specific type of tetromino, similar to the below image example.

Color-coded tetrominoes

Within the rules of Tetris, if any square of a tetromino goes outside of the height boundary (in this case 20), then the game is over. If a row has been completely filled with tetromino squares, however, that row disappears, freeing space above and allowing all above pieces to fall. This means that the largest number of squares that can appear on a given row is 9 and that the overall number of occupied grid squares that can exist at any point in time is $9 \times 20 = 180$.

Assuming that a cell containing a square of color $x$ is not equivalent to a cell containing a square of color $y$ and that an empty cell is not equivalent to any cell containing a square of any color, how many possible boards exist in which the maximum number of grid squares are occupied and no rows have been cleared?

JTstudent
  • 31
  • The “equal chance” thing seems irrelevant if you’re trying to find the maximum (presumably by hand-picking the tetrominos you want. Further questions: does a different order of placement make a board “different”? Does the empty square in each row have to be all in the same column? It’s a cool question, but what suggested to you that it is tractable? – Benjamin Wang Apr 23 '22 at 22:56
  • 1
    You make a good point about the equal chance clause. I have edited accordingly. As for different placement order, I was working on the idea that the only thing that matters is the color of a square, so long as the color does not break any rules by not being attached to other squares of its color in accordance with the shape of its associated tetromino. Similarly, since an empty square is simply an uncolored square, it can be anywhere in each row. As for tractability, I am unsure as to whether it is tractable or not, but am similarly unsure where to start as for proving the tractability. – JTstudent Apr 23 '22 at 23:04
  • My intuition is that this can be brute-forced for small height (say, 4), but the general problem has massively (exponential in the height) huge results. At least, a result for height=4 can be taken to the 5th power to get a lower bound for the result for height=20. – Benjamin Wang Apr 24 '22 at 22:12

0 Answers0