PENTOMINOS
A Puzzle-Solving Program
Jim Butterfield, Associate Editor
Computers can solve puzzles. With the right set of instructions, a program will follow the same logic as humans, trying things to see if they fit. It's interesting to watch the computer working in this way.
This famous puzzle is dealt with at some length in Arthur C. Clarke's novel Imperial Earth. The characters of the novel don't use a computer to solve the puzzle.
The original program works on all Commodore computers. Additional versions are included here for the Atari, IBM PC and PCjr, TI-99/4A, Radio Shack Color Computer, and Apple.
NOTE: IBM, TI, Color Computer, and Apple users should insert lines 110–860 from Program 1, the Commodore version, into their programs. The rem statements at the ends of these lines should be ignored.
Pentominos are like dominos, except that they are made up of five elements rather than two. If we put five squares end to end and glued them together, we'd get a long strip, often called the I pentomino. On the other hand, if we took a central square and glued the other four squares to the sides, top, and bottom, we'd get something that looks like a plus sign, which many people call the X pentomino.
Allowing for the differences that are caused by rotating or turning over a piece, there are 12 different pentominos. They are shown in Figure 1; but you might find it fun to try discovering them yourself by drawing them out on a piece of paper. Most of them look a little like letters—you can see a T, an X, and a W among them, for example.
What's The Puzzle?
The 12 different pentominos, each with an area of 5 squares, give a total of 60 squares. Suppose you had to cut these pentominos out of a rectangle without wasting any space: How big would the rectangle need to be?
We know two things: The total area is 60 squares; and the rectangle must be at least three wide (otherwise, we couldn't cut out the plus sign). So it might be possible to get all the pentominos from a rectangle that is 3 × 20, or 4 × 15, or 5 × 12, or 6 × 10. As it turns out, we can do it in any of these ways.
We can turn the question inside out and put it this way: Can you fit all 12 pentominos into a rectangle of size: 3 × 20, or 4 × 15, or 5 × 12, or 6 × 10?
The Brain Bender
Don't let the following computer program take the fun out of the puzzle for you. Cut the pieces out of cardboard and try your hand at the puzzle. It's an interesting way to wile away the hours. 6 × 10 and 5 × 12 are not too hard; 4 × 15 will make you work; and 3 × 20, which seems at first to be the easiest, proves to be a real brain bender.
A sample solution to the 4 × 15 problem is given in Figure 2.
If humans can waste time trying to fit the pieces, computers can do it too. "Pentominos" does not run at blinding speed; it tries the pieces at about the same speed as humans do. It's dumber than human puzzle solvers: It will try to make a piece fit in places we know instinctively are hopeless. But the computer has no intuition: It will plod along, making dumb moves until it finds a combination that fits.
The program tries the pieces "visibly"—that is, you can see it putting the pieces in place, thinking about its next move, and then taking a piece back out when it becomes obvious (even to the dumb computer) that it can't work there.
In a moment we'll get to more detail on how it works. The computer always thinks about fitting the upper-leftmost empty square, and it will tell you which piece it is trying to fit there; that piece's identity will be shown in a corner of the screen. So you can track the computer's thoughts if you wish.
It can take a few minutes or several hours to find the next solution. This program is a good one to set up for an overnight run. You might want to turn off your TV set or monitor and let the computer hum away quietly all by itself.
When a solution is found, you can type CONT at any blank place on the screen, and the computer will go after the next solution.
How It Works
The pentominos and all their possible rotations are stored in DATA statements. Only four squares need to be described for each pentomino rotation, since the information gives coordinates based upon the starting square.
After reading in the data, the computer uses the following logic. Line numbers are given for those who would like to try examining the program.
- (Line 2010) The computer looks through the list of pieces to find the first one that isn't being used. Then it searches the board for a blank square, starting at the left and searching each column top to bottom. That's the next place it will try to fit a piece. If it can't find a blank, we have a solution and will go to step 5.
- (Line 2030) The piece just picked is set to its first rotation.
- (Line 2060) The computer tries to fit the piece starting at the square it has identified. If it doesn't fit, it will skip ahead to step 7.
- (Line 2120) The piece fits, so the computer puts it onto the board, onto the screen, and marks off the piece as used. It then goes back to step 1 to look for a new place to fit pieces.
- (Line 2170) We have a solution! Stop and wait for the user to admire us. If the user types CONT, we'll keep going into step 6.
- (Line 2190) We've reached a dead end, so we go back and remove the last piece placed on the board. If there are no pieces left, we quit; at this point we will have found all the solutions.
- (Line 2260) Let's rotate the current piece so that we can try it in a different way. If we can find a new rotation, we go back to step 3 to try the piece. If not, we continue to step 8.
- (Line 2300) The computer looks through the list of pieces to find the next piece to be tried. Then it goes back to step 2.
Variables And Arrays
If you're trying to read the program, it will be worthwhile to have some information on variables and arrays. Here are some useful ones:
Array B(X, Y) is the board. If the value is zero, that part of the board is blank. When a board square is used, the appropriate value in this array is set to the number of the occupying piece; but the important thing to remember is that it's set to nonzero.
The DATA statements show all rotations of all pieces. They are transferred to arrays X and Y:
Arrays X(rotation,C) and Y(rotation,C) tell where to find the squares (X and Y) of each piece's rotation. The rotation is taken from the DATA statements.
Array P(rotation) tells which piece is involved for each rotation of the above table.
Each Piece Has Data
Array P$(piece) is the name of the piece.
Array S(piece) tells where to find the starting rotation for piece X.
Array T(piece) tells which rotation is currently being used (or tried) for piece X.
Arrays X2(piece) and X2(piece) list the starting square where piece A has been placed.
Tracking The Moves
Array U(move) lists the pieces in the order in which we tried them.
The piece under consideration is designated by P; its current rotation, of course, will be T(P).
When we place a piece, we log it into array U and use P1 to keep track of how many pieces have been used.
Program Variations
The program could be speeded up significantly by using a compiler or by converting it to machine language. I have chosen not to do that for two reasons: compatibility and readability.
A machine language version would nevertheless be quite straightforward to write. No special math or other logic is involved. Such a program would be very fast. But it would not be universal, since different machines would need to load the program into different memory locations.
If you go for many solutions, you should realize that some of the solutions are transformations of others. Given one solution, others can be found by inverting it left to right or top to bottom. This means that each solution is really four solutions; but the computer will find each of the four as it works. If this is not desired, the extra solutions can be eliminated by removing all but two of the rotations of a single eight-rotation piece. That way, the reflected solutions couldn't happen: That piece can appear in only one orientation.
For example, we could eliminate reflected solutions by changing line 770 to DATA R,2 and then deleting lines 800 to 850 inclusive.
Making It Smarter
The program would run faster if it didn't show its moves on the screen, but watching it work is most of the fun. For one thing, it may remind you of an important aspect of computers: They're dumb, but they're faithful.
The computer will lumber along, trying dumb moves. But it won't get tired, and it will eventually reach the solution.
Yes, we could add extra logic to make the computer smarter. We could ask the computer to scan for some of the obviously impossible situations that it does not recognize at all with the present program. But there's a danger: The computer could waste more time being smart than it does being dumb.