Solving the pentomino problem

What's more fun then solving a pentomino problem? Why, writing a program to solve it for you! This page shows how I went about solving this problem. It's written in Perl but the ideas are applicable anywhere.

The problem

First, lets define the pieces and give them names to make them easy to refer to:

                @           @
  L  @@@@    Z  @@@     X  @@@
        @         @         @

       @         @           @
  T  @@@     F  @@@     Y  @@@@
       @          @

     @ @        @@         @
  U  @@@     P  @@      W  @@
                @           @@

                @
  N  @@@     V  @       I  @@@@@
       @@       @@@

The solution

Next the pieces. You can represent each of those pieces as a list of co-ordinates. For example the L piece above can be represented as [0,0], [1,0], [2,0], [3,0], [3,1]. But wait, each piece can be placed in any of 8 orientations with reflections and rotations. But instead of handling this on the fly, we will expand the set of pieces so that there are 63 of them, but using one will exclude several others. Only 63 because we can remove duplicates. For example, the X looks the same no matter how you place it.

Now we know that the solution will consist of a list of 12 pieces selected from this expanded list. Each piece will have a location describing where it is placed (remeber, we no longer need to worry about orientation). While we now have a better idea of the problem, how to search for solutions is not clear. Do we just lay stuff down rendomly and hope nothing overlaps?

This next part is part optimisation, part simplification. Instead of dealing with a two-dimensional grid, lets turn it into an array. Make it so that the cell at (x,y) is placed at the offset x+12*y. Do the same to the pieces. The important thing to notice is that this does not change how the solution works at all but as we shall see it makes some things much easier.

Take for example the Z piece. We have now converted its four possible positions into simply an array of numbers. If you take the lowest of these numbers and subtract that from all of them, you end up with a list of numbers that are all positive and start with zero. For example, the numbers for Z are:

0, 1,12,23,24
0, 1,13,25,26
0,10,11,12,22
0,12,13,14,26

If you draw a grid and mark the cells, you will see that these indeed represent the four possible layouts of the Z piece. By adding the same number to each of those offsets, we can move the piece to anywhere in the board. A solution now consists of a list of pieces and a single number offset.

Now we can have a clear search pattern. Start at offset 0 in the grid and try to place each piece being careful it's one we have not used yet. Because each list of numbers we have includes a zero, we will fill up the cell we are looking at and so we can sequentially search up for the next free one. When we run out of free calls, we know we have solved the problem.

Moreover, this search will find all possible solutions eventually.

The implementation

After the list of pieces has been made, it builds up the board and then goes straight into solution searching. The search is done using a recursive function for simplicity. First it finds the first free place, using the hint given by its parent. If none left, it prints the solution and returns. Then it tries each piece and tries to place it in the current location. If it fits it places the piece, marks it used and recurses to the next level.

Eventually it will find all the solutions. These are quite a few, more than you would expect while you're trying to solve the puzzle by hand. The perl version will take no more than a few hours on a fast computer. A C version will probably do it much faster. Indeed, for the hexiamonds you need to do it in C to get a result in any reasonable time. This version will find a solution within seconds.

I left it running for 222 minutes and it found 1616 solutions.

Download the source code here.