The trick is to realize that it's only necessary to rotate the pieces 0, 90, 180 or 270 degrees. You can then transform the polygons into a grid problem (each grid square either being filled, unfilled, or partially filled in two different ways), and solve it with backtracking.
