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.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.