Pentominoes

This is Grant Maizels' pentominoes page.

Pentominoes are the twelve shapes that can be produced by joining five squares together continously.

Pentominoes can be arranged to form rectangles 6x10 (2339 solutions), 12x5, 15x4, and 3x20 (two solutions).

I first learnt about pentominoes from the Arthur C Clarke Novel Imperial Earth in the early 80s. After reading this It took 3 days to work out how to arange pentominoes in a 3 x 20 rectangle, with a pencil and paper. About 20 years later I finally got around to writing a brute force program to produce all solutions for a given rectangle.

The program, pent.c , takes one optional argument, (default is 10) the width of the recangle (10, 12, 15, or 20 though 3, 4, 5, and 6 are valid) and performs the following steps.

• Calcuates valid orientations for each piece (removing symetrical versions)
• Calculates valid locations on the rectangle for each piece. This includes ignoring placements which cause segregated parts of the board which are not a multiple of 5 squares (such as occurs if the cross is palced in a corner).
• Startig with the cross tries placing each piece in each valid in the rectangle util it can't place another piece at which point it backtracks. When it suceeds in placing all 12 pieces, it reports the outcome in text. If the -DCHKVD flag is set, then it checks that each void area has a multiple of 5 squares after each placement.

Run Times

When run on my linux machine (Athlon XP-1600 with Red Hat 7.2) we get the following results (real from time) Note: Solutions Found is sometimes double the actual number of solutions because of mirrors:

Compile Option	Width	Time (sec)	Solutions Found
gcc -O3 -DCHKVD	3	7.381	4
gcc -O3 -DCHKVD	4	94.253	402
gcc -O3 -DCHKVD	5	485.103	1308
gcc -O3 -DCHKVD	6	457.847	2339
gcc -O3 -DCHKVD	10	422.453	2339
gcc -O3 -DCHKVD	12	501.863	1308
gcc -O3 -DCHKVD	15	93.267	402
gcc -O3 -DCHKVD	20	5.861	4
gcc	10	49760.787	2339
gcc -O3	10	31949.079	2339
gcc -DCHKVD	10	654.782	2339

Compiling

The program is designed and only tested on Unix/Linux. It can be compiled on Linux with the command:

gcc pent.c -o pent -O3 -DCHKVD

or if you want a slow version

make pent

using some optimisations and the -DCKVD option seem to help make it faster.

Bugs

If the rectangle size selected has an odd number of rows, then mirror image solutions are reported.

Links

• The Pentominoes Page
• Mark's Packing Pentominoes page
• Pentominoes

This page, the linked programs and graphics are Copyright (C) 2003 Grant P. Maizels, Sydney, Australia