Carpets

Even though it may seem too big (7 colors * 7 instances of each color), the problem is a brute force. Create a 2d array of each 1x1 square of the room. For the top-left most uncovered square, iterate over all available carpet options in both orientations. If any of them fit, recurse.

It is difficult to prove this is fast enough, but it is the judge-provided correct solution. Similar to Stained Glass but without the ability to optimize using a bitmask.