How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes

Question

So here's the problem:

-You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid square is empty)

-You must minimize the number of empty grid squares by filling this grid with Tetris shapes which are each composed of exactly 4 blocks (a block is 1x1)

What is an algorithm that can consistently do this given any mxn partially-filled grid?

Answer 1

This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X.

Consider the set of choices you have: For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the board. Let matrix $A$ be our exact cover matrix. The columns of $A$ are the constraints that must be satisfied exactly once i.e. there is a constraint for every unfilled grid location on the given board. Each row represents a "choice" i.e. a tetris piece, orientation and location and has $1$s in only the columns which correspond to the locations that that placement of the tetris piece would cover.

To account for the grid locations that have already been filled, we make sure that any row is removed that would either

• Fall outside of the $m$x$n$ grid
• Cover one of the cells already covered in the given $mxn$ grid

Then it remains to select a subset of rows $S$ such that for each column $i$: $$\sum_{row\in S}row[i] = 1$$

Algorithm X is one way of solving this problem (with the help of the dancing links technique. Other algorithms exist as well (AC3 is taught as an introductory constraint-satisfaction solver algorithm at some universities). Soduku puzzles are another example of exact cover problems.

Notice that max cover is a decision problem, whereas the question you posted is an optimization problem. This can be addressed by just searching for the maximum number of columns covered over the search. Of course this will result in a much slower runtime since you will have to run the algorithm for longer. You may benefit from introducing some heuristics into your search as well. For example, say you are at some point in your search where:

• The best cover you have seen so far covers $s$ locations.
• Your current cover covers $k$ locations.
• There are $x$ remaining open locations on the board that are part of a connected group of at least 4 open locations.

If $k+x\leq s$, you can cut the search tree off here, since there is no way this current layout of tiles can lead to a better solution that the one you have already found.