CENSORSHIP AND RACISM ARE EVIL AND UNAMERICAN!
updated 2001-04-14
Pentominoes
Pentominoes are one of those simple ideas which turn out to be
amazingly complex.
They were re-popularized by Solomon Golomb
in 1953 in a talk to the Harvard Math Club. In his book 'Polyominoes'
(copyright 1965), though, Mr Golomb says that they were discussed heavily in
the 1930s - 1940s in "Fairy Chess Review" (a British puzzle magazine), and
that the underlying concept goes back to ancient times and the masters of Go.
The first known pentomino problem was in "Canterbury Puzzles" in 1907.
____________________________________
It's a simple idea, really. Take 5 squares. Now look at all the possible
combinations of these squares, such that each square touches at least one
other square along a complete edge. There are exactly 12 such configurations,
and, amazingly enough, each one looks like a letter of the alphabet. (OK,
the F and the
N
require a little imagination.)
Here's the 12 letters:
(The coloring scheme is my own. I've played with them so long that these
seem like the only appropriate colors, but that's just me.)
So what's so interesting about this? Consider: There are 12 letters, each of
which is made up of 5 squares, giving a total of 60 squares. The challenge,
then, is to arrange the letters into a 6 x 10 rectangle. Sounds easy enough
until you try it. It turns out there are 2339 different ways to make a
6 x 10 rectangle! Here's three of them:
The first solution above is interesting because it is actually 20 different
solutions. Notice the T
and the F
make a symmetric pair;
that is, you can pull them out, turn the pair around, and put it back in.
The P
and Y
also make a symmetric pair. The
I
makes a symmetric pair with the
P
-Y
combination; and the Z,
U,
and L
make a symmetric group. Finally, the
P
and W
make a symmetric group when the
P
isn't traded with the
Y.
I really didn't like finding the second solution above. For a long time I
had a theory that the
I
had to be on one of the edges. So much for
that idea.
The third solution above is the second one I ever found. Unfortunately, I
don't remember my first one.
When I first made a set of pentominoes, I sat down to play with
them and had a 6 x 10 solution within a couple of minutes. "Hah!", I thought
to myself, "this isn't so hard. Let's find a couple more." So I mixed up
the letters and started again. Three hours later, I hadn't found another
solution, and couldn't remember the first one, and had to get to sleep.
The next night I tried again, and 4 hours later went to bed no closer to
an answer. The next night, I discovered this answer and immediately
memorized it. I'll never forget it.
As you might guess, it's also possible to make a 5 x 12 rectangle and a
4 x 15 rectangle. These are both somewhat easier than the 6 x 10, for some
reason.
The 3 x 20 rectangle is especially challenging. It turns out there are
exactly 2 solutions to this problem, and once you've found one, you also
have the other.
You can also make an 8 x 8 square with the central 2 x 2 square missing,
or an 8 x 8 square with its four corners missing, or lots of other shapes.
Another interesting challenge is the "triplication" puzzle: Choose one
of the twelve pieces, and then use 9 of the others to form a copy of the
chosen piece, 3 times as large in each dimension.
Also quite interesting are the "fence" problems, where you
arrange the 12 pentominoes so as to enclose an empty space.
(The pentominoes must touch along edges, not just corners.)
How large an area can you fence in if the empty space forms a
rectangle, but the pentominoes border is freeform? (I've found an answer of size 90.)
A freeform space in a rectangular border? (I've found one of size 61.)
A rectangular space in a rectangular border? (I've found one of size 28.)
A freeform space in a freeform border? (I've found one of size 128.)
____________________________________
Try it yourself
I've written a Visual Basic program that lets you play with the pentominoes.
Download it and let me know what you think. It's free.
The newest version is 3.5. If you have an earlier version, you really
should upgrade. I've fixed several subtle bugs and made the design option
easier to deal with.
Features:
• 18 pre-defined answer grids to solve, some of which you can modify for
additional challenges
• the Triplication puzzle, mentioned above, for 12 more challenges
• a Design option, which lets you create your own puzzles by
arranging the answer grid in whatever shape you want.
You can click and drag to "rubber band"-select and move large sections
of the answer grid.
• a Freeform option, which lets you play with the pentominoes without
any defined answer grid
• an AutoSolve button, which will find a solution from a given
starting point. AutoSolve can find more than one solution,
or even search out all possible solutions.
• an option to not show progress during AutoSolve, which
makes it much faster (but less fun)
• an option to play the competitive game (see below), with three levels
of difficulty, using 15 different playing boards
• the ability to save your work in files for later display (a samples
file is included)
• (32 bit version only) an option to be able to open
these files by double-clicking on them.
Take your choice:
32 bit (For Windows 95 or later)
The program is here:
Pentominoes 3.5 (32bit) (zipped, 67K)
You also need a bunch of support files for this version, but you
probably already have them. Search your computer for files
named comdlg32.ocx and olepro32.dll . If they aren't there, you'll need
to download the
VB4 support files (zipped, 802K(!)).
And all VB4 programs need the file vb40032.dll, which should be
in your /windows/system directory. You probably have it already, but
if not, it is available from many places on the Web. Try any of the
popular shareware Web pages, or just use a search page to find it.
Here is a link to download it from
Microsoft.
(Get the Version 4 file.)
16 bit (For Windows 3.x users)
The program is here:
Pentominoes 3.5 (16bit) (zipped, 56K)
It requires a support file, named vbrun300.dll ,
which should be in your /windows/system directory.
If you don't have it, it's widely available. Any of the Web search engines
should be able to find it for you. It's on the Win95 CD, too.
Here is a link to download it from
Microsoft.
(Get the Version 3 file.)
I'm seriously thinking of writing a 3D version of this program (see
below), but it's looking difficult so I might have to make it not free.
____________________________________
Pentominoes as a Game
The first place I read about pentominoes was Arthur C. Clarke's book
"Imperial Earth", where they are used in a subplot.
In the afterword
of the book, Mr. Clarke mentions that Mr. Golomb invented a game based
on pentominoes. This game has very simple rules (players alternate
placing a piece on an 8x8 square; the last one to play a piece wins),
but is quite challenging.
There are 347 different starting plays, and over 1600 responses for
most of them (I think). Games usually last about 8 plays, and so don't
take much time. It is an interesting game.
Note: Hilarie Orman, while at the University of Arizona, proved that, on
an 8x8 board, the game is a win for the first player. (I didn't
use this fact in my program.)
____________________________________
Solid Pentominoes
I made my first set of pentominoes out of cardboard, and they quickly got
thrashed. The next set I made out of wooden cubes, which gave me an idea.
Since there are 60 squares (cubes), is it possible to make a 3 x 4 x 5 box?
It turns out it is. For example:
I found about thirty solutions, and then wrote a program to search for
others. It found 3940 of them!
There are many other interesting shapes you can make with the solid
pentominoes. For example, you can make a scale model of each of the
letters (except W
and X),
twice as long and twice as wide, three units high.
____________________________________
More Info
There was an article about pentominoes in the May 1957 edition of
Scientific American. They also have appeared many times since then in the
Mathematical Games column of that magazine.
Solomon Golomb's book "Polyominoes" has quite a bit of information about
pentominoes.
There is now a second edition of this book.
(Princeton University Press; ISBN 0-691-08573-0)
The popular computer game Tetris is basically the same concept as pentominoes,
but with 4 squares instead of 5.
The old Soma Cube puzzle was a 3D, 4-cube version. Actually, it didn't use
all the possible combinations.
Phillipe Laurent has
a Pentominoes page
which goes into detail on the triplication problem.
The students of T.I.D. - Ronse school in Belgium have
a nice Pentominoes page
with a clever Excel spreadsheet to do the fence puzzle. They also have
occasional pentominoes competitions, where you are challenged to find the
best solution to a puzzle.
____________________________________
Rotations and Reflections
(for the more theoretical-minded)
Just how many solutions are there to the 3 x 4 x 5 puzzle?
That turns out to be an interesting question, and not quite as easy
to answer as you might think.
First, to establish some terminology:
Consider the 3 x 4 x 5 solution above. Call the axis that is 5 boxes
long the x-axis, call the 4-box axis the y-axis, and call the 3-box axis
the z-axis.
Assign the coordinates (1,1,1) to the completely hidden corner in
the above picture, and number the rest from there, so that the top of the
T
is at coordinates (5,4,3) (the completely visible corner above).
Now, number the 12 pentominoes in alphabetical order, so
that F=1,
I=2,
L=3,
..., Z=12.
Notice that each of the pieces also can be oriented several different
ways. The F and
P
each have 24 possible orientations;
the L,
N,
and Y
each have 16 possible orientations (it would be 24 if the puzzle weren't 3 units high);
the symmetric letters T,
U,
V,
W,
and Z each have 12; the doubly-symmetric
X
has 3; and the doubly-symmetric
I
has only 1 (it would be 3 if the puzzle were 5 units in each dimension).
Consider the 3 x 4 x 5 solution on the left below. If we
pick it up, flip it around the x-axis, and put it back down, it
becomes the solution on the right below.
Are these different solutions?
Every
letter is in a different place or orientation, but obviously these can't
really be called "different" solutions. Similarly, any combination of
rotations about any axes won't make a "different" solution. So,
to properly count the number of solutions to the 3 x 4 x 5 puzzle, we
have to skip ones that are simple rotations of other
solutions. Is there a way to identify these duplicate solutions?
One seemingly easy way is to fix the location of the
I.
Since it's 5 units
long, the only way it will fit is lined up along the x-axis, which means
there's only 12 possible places it can go. We've already seen that
the I
going from (1,1,1) to (5,1,1) is equivalent to having it go from
(1,4,3) to (5,4,3); one more rotation will also show that the other
two corners are also equivalent. By a suitable combination of
rotations, the 12 possibilities can be reduced to 4 distinct ones:
One end of the I
must be at (1,1,1), (1,2,1), (1,1,2), or (1,2,2).
The solutions thus can be grouped into four categories, based on
where the I
is located.
Categories three and four, with the
I
in the middle layer (z=2),
require a slight refinement, however.
Notice that for these solutions:
A rotation about the x-axis moves the
I
to (1,4,2) for category three,
and (1,3,2) for category four. Both of these are not valid positions, but
a rotation about the z-axis corrects that. In either case, the piece at
(1,1,1) is traded with the piece at (5,1,3).
A rotation about the y-axis leaves the
I
in place, but switches the top and bottom layers. (Actually, the
I is flipped,
but it's the same as if it didn't move.) Again the
piece which was at (1,1,1) gets moved to (5,1,3) and vice versa.
A rotation about the z-axis moves the
I to (1,4,2)
for category three, and (1,3,2) for category four. Both of these are not
valid positions, but
a rotation about the x-axis corrects that. In either case, the piece at
(1,1,1) is traded with the piece at (5,1,3).
Thus a distinct solution in category three or four will have two possible
orientations, which are equivalent by a rotation about the y-axis.
Since it is impossible for a single pentomino to occupy both (1,1,1) and
(5,1,3), one of these two orientations will have a smaller-numbered piece
at (1,1,1). Let's say that this is the 'true' orientation of the solution.
Our rule for eliminating simple rotations is thus:
1. The I
must be located at (1,1,1), (1,2,1), (1,1,2), or (1,2,2).
2. If the I
is in the middle layer, the piece at (1,1,1) must be
alphabetically smaller than the piece at (5,1,3).
Now a more tricky problem.
Consider the two solutions below. Notice that the solution on the right
is a mirror image of the solution on the left.
Are these different solutions?
Again, the letters are all in different places or orientations, but
again it seems wrong to call these "different" solutions. Notice, though,
that the solution on the right cannot be made by any combination of rotations
of the solution on the left. Our trick of fixing the location of the
I
doesn't really skip all the duplicate solutions.
Is there a way to tell if a
solution is a combination of reflections and/or rotations of another solution?
Let's examine each of the four categories:
Consider a solution S of the first category, with the
I at (1,1,1);
and in particular notice the piece at (1,2,1)
(F
in the solution on the left above) as various reflections are applied.
When S is reflected through the xz plane to make a new "solution" S',
the I
moves to (1,4,1). This is not one of the four valid positions, so
we must rotate S' about the z axis. Call the result S''.
S'' is thus equivalent to S by reflection. Notice that the piece at (1,2,1)
in S has moved to (5,2,1) in S''.
When S is reflected through the yz plane to make a new "solution" S',
the I
remains at (1,1,1). S' is equivalent to S. Notice that the piece
at (1,2,1) in S has moved to (5,2,1) in S'.
When S is reflected through the xy plane to make a new "solution" S',
the I
moves to (1,1,3). This is not one of the four valid positions, so
we must rotate S' about the y axis. Call the result S''.
S'' is thus equivalent to S. Notice that the piece at (1,2,1) in S has
moved to (5,2,1) in S''.
This means that any odd number of reflections is equivalent to a single
reflection through the yz plane. (An even number of reflections yields
the original solution.) Thus, each solution in category one has two
orientations that are equivalent by reflection.
Since it is impossible for a single pentomino to occupy both (1,2,1)
and (5,2,1) (except the
I,
which by definition is
placed elsewhere), one of the two orientations will have a smaller-numbered
piece at (1,2,1). Let's say this is the 'true' orientation.
Thus, if we specify that the piece at (1,2,1) must be smaller
alphabetically than the piece at (5,2,1), we can eliminate all solutions
in the first category which are reflections of another solution.
For category two (the I
at (1,2,1)), the same argument holds, except
that the locations to be compared are (1,1,1) and (5,1,1).
Categories three and four again require further restriction.
As above, reflection through the xz plane followed by a rotation about
the z axis leaves the I
in place and moves the piece at (1,1,1) to (5,1,1).
Also as above, reflection through the yz plane leaves the
I in place and
moves the piece at (1,1,1) to (5,1,1).
Now, though, reflection through the xy plane leaves the
I in place, and
moves the piece at (1,1,1) to (1,1,3). A rotation about the y-axis moves
the piece to (5,1,1), but is not required to keep the
I
in a valid position.
Thus, solutions in these categories have three orientations which are
equivalent by reflection (and a fourth by rotation, as shown above).
The piece which is at (1,1,1) in one of the orientations is mapped to the
other three corners of the xz plane in the others.
Since we've eliminated one of these orientations
by saying the piece at (1,1,1) must be smaller than the one at (5,1,3),
it makes sense to extend the rule by also eliminating all orientations
where the piece at (1,1,1) is not the smallest of the four corners in that plane.
While it is impossible for a pentomino to occupy (1,1,1) and (5,1,1)
(except the I,
which by definition is placed elsewhere), it is possible
for one pentomino to occupy (1,1,1) and (1,1,3). This happens with the
U
in category three, and with the
P,
T,
U,
and V
in category four.
These solutions, then, require further restriction.
The problem with these solutions is that after a reflection through
the xy plane, they appear to still meet the qualifications for a
true solution: The piece at (1,1,1) is still the smallest of the four
corners. Notice, though, that this reflection trades the pieces at
(5,1,1) and (5,1,3), so again we can distinguish them by choosing the
one with the smaller piece at (5,1,1).
Naturally the question arises: What if the piece at (1,1,1) is also at
(1,1,3) AND the piece at (5,1,1) is at (5,1,3)? This can happen in
category 4, since the
P,
T,
U,
and V
could each potentially occupy two corners.
Indeed there are solutions of this form. The logical extension of
the rule is then to proceed to the other corners, and specify that
the piece at (1,4,1) must be smaller than that at (1,4,3); and, if
necessary, that if these are equal then the piece at (5,4,1) must be
less than the one at (5,4,3).
Fortunately, there are no solutions (according to my program)
in category 4 which
have all four sets of corners matching. There is however, a solution
with three sets:
To recap, then:
When counting distinct solutions to the 3 x 4 x 5 puzzle, we must skip
any which are equivalent to some other solution by a combination of
rotations and reflections. One way to do this is to label a solution as
valid only if these criteria are met:
1. The I
must occupy one of these four positions: (1,1,1), (1,2,1),
(1,1,2), or (1,2,2).
2. a) For the first category, the piece at (1,2,1) must be alphabetically
smaller than the piece at (5,2,1).
b) For the second category, the piece at (1,1,1) must be smaller
alphabetically than the piece at (5,1,1).
c)For the third and fourth categories, the piece at (1,1,1) must be
less than or equal to the pieces at (1,1,3), (5,1,1), and (5,1,3).
If the piece at (1,1,1) is also at (1,1,3), the piece at (5,1,1) must
be less than or equal to the piece at (5,1,3). If equal, the piece at
(1,4,1) must be less than or equal to the piece at (1,4,3). If equal,
the piece at (5,4,1) must be less than the piece at (5,4,3).
According to my program, the count of distinct solutions is:
| Category 1: | 2715
|
| Category 2: | 358
|
| Category 3: | 337
|
| Category 4: | 530
|
for a total of 3940 different solutions.
Pretty amazing how far astray you can go starting with just 5 squares, isn't it?
____________________________________
copyright 1996 - 2000 by Ken Hinds
All rights reserved.
____________________________________