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?

It may be late for me: how about stacking horizontal Is from the left, vertical ones from the right? Should give three cleared rows in the example, and a start at a greedy heuristics. — greybeard, Aug 09 '15 at 20:13
@Gene. no, I found dp solution for a little more general case which is exponential on W. I thought maybe further simplifying and allowing only 2 types of tetramino I could solve it in polynomial time but I couldn't. — xashru, Aug 09 '15 at 20:23
@greybeard you are right, it does clear 3 rows. I have edited the example. — xashru, Aug 09 '15 at 20:37
The heuristics approach would probably work, as the problem is relatively simple. You would need to design a set of rules depending on the size of the board (eg. if its very wide, place the '--' side by side, if not, pile them up). — Joaquin Rocco, Aug 09 '15 at 20:43
@Gassa both questions are already answered in the original text — Juan Lopes, Aug 09 '15 at 21:14
@JuanLopes Thank you, I see the answers now that I read it again. Silly me. — Gassa, Aug 09 '15 at 21:47
Are the solutions allowed to guide pieces sideways into holes in the board that are inaccessible from the top due to overhangs? For example, on a 5-width board with the piece sequence `||-|||` you're forced to create an overhang with the `-` and then move the later `|`s under it if you want to clear 4 rows (instead of 1 or 0). — Craig Gidney, Sep 10 '15 at 15:20

Ortomala Lokni · Answer 1 · 2016-03-21T07:25:17.873

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.

Emmett Casey · Answer 2 · 2016-03-20T13:58:48.043

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.

Polynomial time solution for Tetris Puzzle

2 Answers2