## IPSC 2004

## Solution to Problem T – The Tiling Problem

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.