A friend of mine told me he think he came up with an algorithm for solving the covering problem. He asked for my help in demonstrating / proving it.

The covering problem (or at least the variant I’m dealing with) is: given an area composed of squares (the area may be any shape, connected), and a cell, also composed of squares, what is the minimal number of cells needed to cover the whole area?

A simple example of the covering problem I was presented with may be this:

Take a chess board, with N (N>=0) of its squares removed, but in such a way that it’s still connected (one area).

Now, take a simple shape – say a domino like 1X2 element, or a cross-like element (a center piece, and its immediate neighbors to the E, W, S, N).

How many elements are required to cover the whole area?

elements may overlap, and they may “cover” squares outside of the area. They may not be turned, though.

Someone on another board I frequent suggested it is similar to the set cover problem. Are the two problems identical? If not, is it a well-known problem? Is it NP or P? Are there any / many algorithms to solve it?

Thanks!