Polynomial time solution for Tetris Puzzle

Question

This is a puzzle based on Tetris. In this puzzle we are given the sequences of next n pieces that are going to fall from top. Our job is to maximize the score before its GameOver. There is no polynomial time algorithm known for the general Tetris but in this puzzle only the I (straight) tetrominoes are allowed. Though its not allowed to rotate them.

So here are the constraints:

• The board is a W x H rectangle
• We are given the sequences of next n tetrominoes
• Only I tetrominoes are allowed (horizontal or vertical)
• Piece rotation is not allowed
• Rows are cleared as they are filled up
• Board is initially empty
• 1 point is awarded per row cleared.
• Game is over when tetrominoes stack up to the top of the playing field.

Find the maximum score that can be obtained.

Example:

8 x 6 board. Next 7 tetrominoes are [——,|,|,——,|,——,|] where '——' represents horizontal I tetramino and | represents vertical I tetramino.

Maximum possible score in this case is 3 using following strategy ('.' represents empty board, '#' represents part of tetramino piece).

Initially:
........
........
........
........
........
........
1st move:
........
........
........
........
........
####....
2nd Move:
........
........
.......#
.......#
.......#
####...#
3rd Move:
........
........
......##
......##
......##
####..##
4th Move:
........
........
......##
......##
####..##
####..##
5th Move:
........
........
.....###
.....###
####.###
####.###
6th Move:
........
........
.....###
####.###
####.###
####.###
7th Move:
........
........
....####
########
########
########  // bottom 3 rows are cleared so score is 3
final state:
........
........
........
........
........
....####

Even the best algorithm I could come up with takes exponential time where I am saving the state of the top layer of the current board (i.e. how high each column is). So this algorithm will take O((H^W)*n)time since for each column there are H possibilities for height.

Can this be solved in polynomial time using dynamic programming or some greedy algorithm?

Answer 1

I will try a guess:

The board is a W x H binary matrix.

The sequences of tetrominoes is a binary string s of length n, 1 for vertical, 0 for horizontal.

Let's try the decision problem: Given an arbitrary board and an arbitrary sequence s of tetrominoes of length n, is there a winning sequence of move ?

At each step you can do at most W choice : the position of the tetronmino.

To check if for given a board and a sequence of tetrominoes there is a winning sequence of move check CanWin(B(n)) with the following algorithm:

 CanWin(B(i)):
   if Filled(B(i)) return false
   if (i == n and not Filled(B(i))) return true
   choose position in 0..W-1
   B(i+1) = UpdateBoard(Bi, s(i+1), position)
   return CanWin(B(i+1))

You can check if a board is fill in O(W) by checking the top row. You can update the board by checking collisions in O(H). [Need to take into account row erasure] Then you can decide if there is a winning sequence in O(nW(H)^W).

If you remember which guess was the best with parent pointers, you then have a winning strategy.

Now the algorithm is exponential but you can memoized the recursion with a dataset which the size is at most 2^(W x H + 1) x W.

Since now, I don't know how to count the number of memoized calls.

Remarks:

• In this version you can't guide the tetromino during the fall from top.

• There could be cycles in the recursion because of the row erasure. You should maybe remove this rule from your problem.

• The article Tetris is Hard, Even to Approximate conjectures in the conclusion that Tetris with only one horizontal/vertical tetromino is polynomial time.

Answer 2

I cannot fathom how this could be done faster than exponential time worst case. Some thoughts:

Game ends when either: n tetrominoes are placed or placed tetrominoes go above losing level.

A solution may be found faster than exponential time. Since the only way to accumulate points is to clear rows, and since it is 1 point per row no matter how many rows are cleared at once, there may exist multiple solutions. If no tetrominoes remain on the board after placing n tetrominoes, then there is no higher scoring solution possible (finishing in less moves is not awarded bonus points). In the best case, a solution can be found in linear time (place n tetrominoes), worst case is exponential.

There are obviously tricks or patterns we could employ to speed things up. For instance, if x number of tetrominoes can be proven to clear the board, then if x divides n we have a solution.