You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), while it's not allowed to cover missing tiles. Currently, I solve it using the following greedy algorithm:
for x in N: for y in M: insert a tile at (x, y) if it possible for x1 in N: for y1 in M: insert a tile at (x1, y1) if it possible remove the tile
I'm sure that it's not the right way to approach this problem, but it passes all tests that are interesting to me. There is a somewhat similar problem, but I doubt that I can reuse it in mine settings. I think that it could be solved by backtracking, but I'm stuck at this point.
Example. Orange pieces are missing.