Solving the pentomino problem

Up: Puzzle solving by computer  
Prev: The cube puzzle   Next: The hexiamond puzzle  

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

Here I deal specifically with the problem of fitting the 12 pentominos into a 6x10 grid. This is the version available as a game and is how I first came in contact with this puzzle. Even after I solved it I was curious as to how many solutions there were.

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  @@@@@
       @@       @@@
Note that this is all possible pentominos, there are no others (ignoring reflections and rotations). Now you just have to fit them into a grid that is 6x10. This is not a difficult problem but it will take you quite a while!

The solution

The first problem is describing it in a way the computer understands. The computer does not know what a block is or what a grid is. So the first step is to define an two-dimensional array that defines the size and shape of the problem. So we will deal with an 8x12 grid, with a filled in border on each side.

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

The implementation here is very similar to what I described above with a few additions. For example I did not want to work out all the numbers for the pieces by hand. So I simply defined a string for each piece which started somewhere in the piece and then went up, down, left or right until it had gone to each square. It doesn't matter if you visit the same square more than once, the program can sort that out. Similarly it contains a list of rotations and translations and applies them all, stripping out repeats. This is what the ParsePieces function does.

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.


Up: Puzzle solving by computer  
Prev: The cube puzzle   Next: The hexiamond puzzle  
By Martijn van Oosterhout (kleptog (at) svana.org)
Copyright © 2000-2006 - Last modified 3/04/2006