Pentominos

Pentominos are objects that are made by gluing five squares of equal size together. The object must be continuous (no separate pieces) and were the squares are glued together, they must share an entire edge. Here is an example of a pentomino.

There are 12 different pentomino shapes, each one of which is designated by a letter. The following is a list of the shapes and the letters that go with them.

Since there are 12 pentominos, and each pentomino has five squares, that makes 60 squares all-told. The objective of the pentomino puzzle  is to start with a rectangle containing 60 squares (5x12, 6x10, 4x15, or 3x20) and attempt to fill the entire rectangle using one, and only one, of each pentomino. The "standard" board is 5x12, as illustrated below. Click on the buttons to either solve the puzzle or show the solution. The computer uses a technique called "back-tracking" to find the solution. Clicking on the "solve" button will tell the computer to show its progress as it searches for the solution. The "Show Solution" button causes the computer to search for a solution and display it without showing intermediate results. In both cases, the computer actually solves the puzzle to find the solution, rather than simply displaying a "canned" solution. There are several thousand solutions to the puzzle. The program stops when it finds the first. The same back-tracking technique could be used to find all solutions, but this would take a very long time.

In working through the solution to the puzzle, it is necessary for the computer to know more than just the shape of each pentomino. When a pentomino is placed into the diagram, it can be rotated, or flipped-over to make it fit. Each pentomino has several orientations in which it can appear. The number of different orientations depends on the shape. For the shape U, there are four different orientations, which are illustrated below.

The shape K has eight different orientations, which is the maximum for any shape.

The shape I has two orientations, and the shape X has only one.

The orientation numbers are, of course, arbitrary. The program that solves the puzzle has a complete list of all shapes as well as a complete list of orientations for each shape.

Now take a look at the solution of the 6x10 board. Finding the solution will take much longer than for the 5x10 board, so be patient.

If we were to slow down the solution process, it would be more apparent how the computer goes about finding its solution. The computer goes through the diagram, one square at a time starting at the upper left. First, it goes down the leftmost column, attempting to fill each square with a pentomino. When it finishes with the first column, it begins at the top of the second column, and continues until the entire diagram is filled. When it finds an empty square, it chooses the first unused pentomino an attempts to put it in the empty square. It starts with the first orientation of that pentomino, orientation zero. Two things can go wrong when trying to place a pentomino into the diagram. The new pentomino can overlap a pentomino that it already put in the diagram, and the new pentomino can extend beyond the edges of the diagram. If either of these things happens, the computer rejects that orientation and goes on to the next orientation. If it tries all orientations of a pentomino, and none of them fit, it goes on to the next pentomino. When a pentomino fits, the computer draws the pentomino in its new position, and goes on to the next empty square. Every time the computer puts a pentomino into the diagram, it keeps track of the empty square it was on when it placed the pentomino, the shape of the pentomino, and its orientation. If the computer runs out of pentominos, and can't fill a particular square, it goes back to the last pentomino it placed, and takes it out. Then it tries the next orientation of that pentomino, continuing until it places a different shape or orientation, or until it runs out of pentominos. If necessary, the computer will go all the way back to the beginning and try a different orientation or pentomino in the upper left. The process of removing pentominos and going back to the previous position is known as back-tracking.

Now try the 4x15 board, and watch how back-tracking is used to try different configurations of pentominos.

And Finally, the 3x20. This solution will require the computer to back up all the way to the beginning and try a different orientation of the first shape.