[AMOF] [GENERATE] [Schoolnet Icon]


Information on Pentomino Puzzles

[Description | Example | History | Applications | Implementation | Classroom | Links]


Description of the Problem

A pentomino is an arrangement of 5 unit squares (or sometimes cubes) that are joined along their edges. Up to isomorphism (rotating and flipping), there are 12 possible shapes, which are illustrated below. Each piece is labelled by the letter that most accurately reflects its shape.

[] [] [] [] [] []
[] [] [] [] [] [] []
[] [] [] [] [] [] []
V T W X

[] [] [] [] [] []
[] [] [] [] [] [] []
[] [] [] [] [] [] []
U Z F P

[]
[] [] [] []
[] [] [] [] [] []
[] [] [] []
[] [] [] [] []
I N Y L

The problem is to fit the 12 pentomino pieces into various shapes, often rectangles. The rectangular shapes that fit all 60 squares are of sizes 3x20, 4x15, 5x12, and 6x10.


Example

Here's a solution to the 6 by 10 puzzle using the letter encoding.

NFVVVYYYYI
NFFFVLLYZI
NNFXVLZZZI
PNXXXLZWTI
PPUXULWWTI
PPUUUWWTTT

Much better looking is the same solution using tables and gifs ("gif" refers to a standard format in which pictures are encoded in web browsers).

-


A Brief History

The first published solution to a pentomino puzzle appeared in Henry Dudeney's The Canterbury Puzzles in 1907. Dudeney presented a solution to a puzzle of fitting the twelve pentomino shapes together with one square tetromino--four squares joined together-- on a 8-by-8 checkerboard. This puzzle is considered the oldest of the pentomino puzzles and it comes with a fictional story. The story goes that the son of William the Conqueror and the dauphin of France were playing a game of chess when the dauphin threw the chessboard at his opponent in a fit of frustration. The son of William the Conqueror retaliated by breaking the chessboard over the dauphin's head, breaking the chessboard into thirteen pieces--12 pentominoes and 1 tetromino--which then had to be put back together.

From the 1920s through the 1950s, many solutions to Dudeney's puzzle as well as other pentomino patterns appeared in a British publication called The Fairy Chess Review. Many of the most interesting results were summarized in the same publication in its December 1954 issue.

Also in 1954, Solomon W. Golomb published an article, "Checker Boards and Polyominoes", in American Mathematical Monthly, in which he introduced the term "polyomino" and defined it as a "simply connected set of squares" joined along their edges. From this term and its definition came the word pentomino, to represent the five connected square shape. Golomb's 1965 book, Polyominoes, is the classic reference to polyominoes.

There was a great deal of interest in the pentomino problem following these publications and, in 1958, a computer was programmed to generate solutions for a 8-by-8 checkerboard form. An exhaustive list of 65 distinct solutions were found, not counting additional solutions that can be obtained by rotations and reflections.

It is now also known that there are 2339 solutions for the 6 x 10 rectangle; 1010 solutions for the 5 x 12 rectangle; 368 solutions for the 4 x 15 rectangle; and 2 solutions for the 3 x 20 rectangle.


Applications to Mathematics and Other Areas

Pentominoes puzzles form an interesting branch of recreational mathematics, but they don't have a lot of application in mathematics. From the research point of view, there are many unanswered questions about their generalizations, the polyominoes. For example, it is not known how many polyominoes may be formed with 100 squares. Mathematicians often find clever formulas for counting, but no one has yet discovered a formula for the number of polyominoes; perhaps none exists!

What is the best way to cut cloth into patterns so the least amount of cloth is wasted? This is a very important question for the garment industry and variations of it occur in many other industries. If the patterns were the pentomino shapes then you now know that you could cut a 6 by 10 rectangle of cloth and not waste any. But what if the patterns weren't pentominoes? What if you had to cut 12 copies of the X shaped piece from a roll of cloth 6 units wide? There would certainly be some waste, but exactly how much cloth is required? The answer to these types of questions is usually not easy. Playing and experimenting with pentominoes can give you some intuitive feeling for the complexity of these types of problems. Mathematicians call them two-dimensional packing problems.


Explanation of AMOF implementation

There is no direct way to list solutions to pentomino puzzles. You have to try all possibilities. The technique we use is called backtracking. This is a well-known recursive programming technique used in solving many different types of problems.

In the generation page of this program, you can choose one of the predefined rectangles or customize the shape by clicking on 60 of the small squares to define the shape that you want to create using the 12 pentominoes. Following are some examples of the various shapes and sizes that you can create with 12 pentominoes:


Using Pentominoes in the Classroom

The pentomino puzzle is a popular choice for a classroom manipulative to facilitate learning how shapes can be transformed or arranged in a predefined shape and space by simple rotation, reflection, and translation. The pentomino puzzle is readily available and also easy to make. It is a fun way for students as young as grade 3, to learn the basic concepts in tranformation of shape and space.

Learning to identify, create, analyse, and describe designs using combinations of slides (translation), flips (reflection), and turns (rotation) is part of the math curriculum in British Columbia and in Ontario, from grades 3-10. The use of computers to create designs using combinations of slides, flips and turns is suggested as a resource in the Ontario curriculum guideline.

AMOF is just such a resource. It can be used to create and analyse many different designs and patterns using the 12 pentomino pieces within a specified area (consisting of 60 squares) and shape (rectangles or a custom shape), using combinations of slides, flips, and turns.

Some of the problems given in the example section should give you some idea of how many different shapes and sizes can be created using the same 12 pentominoes simply by sliding, rotating, and flipping the pieces.

There is a specific reference to Pentominoes in the widely used textbook series, Houghton Mifflin Mathematics for grade 10. Finding one of 65 solution to arranging the 12 pentominoes on a 8-by-8 square with a 2-by-2 square in the middle is given as an extra credit problem in the book. This is a very difficult problem to solve. Students can try to solve the problem on their own using manipulatives, to get a feel for the actual movement of sliding and flipping the pieces, then use AMOF to generate and see up to 10 of the 65 solutions. Now that the students know what some of the solutions look like, they can try to find one of the solutions not generated by AMOF.

The following are some resource materials on Pentominoes recommended by the B.C. Ministry of Education's Math Curriculum Guideline (1995):

These are all in print form. AMOF is unique in that it is interactive, giving the user immediate feedback on design ideas and on analytical reasoning, and it is guaranteed to find a solution if one exists.

Suggested Questions for Students:


Links to Other Relevant Sites and Sources of Information

For more information on pentominoes consult the classic book by Solomon W. Golomb, Polyominoes, Scribner's, New York, 1965, or the more recent book Polyominoes (A Guide to Puzzles and Problems in Tiling) MAA, 1991, by George E. Martin.


[AMOF] [GENERATE] [Schoolnet Icon]


This page created by Frank Ruskey and Susan Ruskey, June 1996. ©Frank Ruskey and Susan Ruskey, 1996.