Tetromino tiling.

Question

There is a rectangle grid given with some of the tiles already filled with tetrominoes. I want to find out the minimum number of tetrominoes required to fill the remaining tiles such the filling is perfect. By perfect , the tetrominos used to fill the grid should not extend outside the grid.

This is a programming problem which I intend to solve using backtracking. But I want to learn the math behind it. Is it possible for me to find out if a perfect tiling is possible. And If yes is there a greedy way to fill in the grid with minimum number of tetronimos.

Answer 1

You don't define your problem very clearly but under any interpretation there are no really easy answers. I assume that you have some squares you wish to cover, some you don't care if you cover or not ("already covered") and some you must leave uncovered ("outside the region") You seem to permit overlapping tetrominos but would prefer to use as few as possible (so no overlaps if possible) There are seven tetrominos (or five if you allow reflections). Are you saying that you can use any mix of them?

It is a pretty well worked out, but far from trivial matter to say how many ways one can fill an empty rectangle with dominoes. So any version of your question would be difficult (even using only 1x4 and 4x1 tiles). There are various simple and not so simple criteria for a perfect tiling but they are usually applied to the situation with all tiles congruent. One can translate certain NP complete problems into simple seeming exact cover tiling problems so in general there is decision algorithm.

If you say no overlaps then this is one example of packing/exact-cover as are Soduku and the n queens problem. After you write your program you should check out this amazing algorithm of Donald Knuth.