The easy input could easily be solved by trying all possibilities (i.e. using a backtracking algorithm). The hard input was much too large for this approach to work. A more clever idea is needed.
Suppose we color the plan like a chessboard. Note that each tile covers one black and one white square. Also if the numbers of black and white squares differ there is no solution.
The condition stated above is necessary, but not sufficient. Moreover, we have to find a solution effectively, if one exists. We will use the following idea:
Consider a graph with vertices corresponding to the unit squares of the plan. Two vertices are connected by an edge iff the corresponding squares are adjacent. This graph is clearly bipartite – one possible partition of the vertices corresponds to black and white squares in chessboard coloring. Each tiling of the whole plan corresponds to a perfect matching in our graph – each square=vertex is covered by exactly one edge of the matching=tile.
There is a trivial polynomial-time algorithm to find a maximal matching in a bipartite graph. The idea of the algorithm: Start with an empty matching. If we have a matching, either there is an augmenting path (a path connecting two unmatched vertices, using alternately a non-matching and a matching edge) or the matching is already maximal. If we have an augmenting path, we can create a larger matching by switching the edges of the path (i.e. the non-matching edges become matching edges and vice versa). We can easily find an augmenting path (if one exists) using a breadth-first search starting in unmatched vertices of one partition.
After we found the maximal matching, it suffices to check whether it is perfect or not.