Tiling with Pentominoes [40B]

Contributed by Raoul Gough

There exist twelve plane figures made up of five 'properly' joined equal sized squares. These can be tiled in various ways to fill a rectangle of size 6x10, assuming the equal-sized squares have unit area. Write a program to find a suitable tiling. Extend it to count the total number of possible tilings. Extend it to tile areas of different shape, such as 5x12 or 3x20 rectangles, or even arbitrary figures of the correct surface area.

You can find the twelve pentominoes here.

Program elements

Should re-enforce: Recursive algorithms, data representation including collections, encapsulation (e.g. member functions to test "fit" of a piece in the grid, cycle through rotations, etc.)

Hints

Those who want to think about a solution for themselves should skip this bit! IIRC, the best approach I found was to try and fill the smallest unfilled area using any available pieces, which tended to detect "impossible" regions quickly. This combined with recursion and backtracking, of course. A previous implementation tried to place the next unused piece anywhere in the grid, which wasn't quite as good.

Extensions

The above link for pentominoes will take you to a site that lists quite a number of other pentomino based problems that are well suited to programming projects.

There is one special case tiling which is to tile a chessboard (8 by 8) with the twelve pentominoes and a two-by-two block. Writing a computer program to determine how many solutions there are is quite demanding (about level 60).

There are many other questions about pentominoes but I leave that to your imagination.

General Solution

Gerard Putter has a 'general' polyomino solver written in Java. I have placed the general in quotes because it does require information about the polyominos to be used in the solutions. I do not think the existence of such a program should deter you from trying your own. However the existence of a working program shows that it is possible.