Homepage(german)     Computer stuff(german) [deutsche Version]     [version française]

The pentomino puzzle

This is a rather known puzzle too: 5 squares are put together in all possible ways. 12 tiles can be formed this way, the "pentominos". Now the task is to lay certain forms, for example rectangles. Although there are e.g. 2339 solutions for the 6x10-rectangle (plus solutions, which can be derived from these via rotation and reflection), it is not so simple to find even one of these with hand. The problem seems to be made for computers.


+---+---------------+---+-----------+-------+---+-------------------+---+-------+
|   |               |   |           |       |   |                   |   |       |
|   |   +-------+---+   +---+   +---+   +---+   +-------+-------+---+   +---+   |
|   |   |       |           |   |       |   |           |       |           |   |
|   +---+---+   +-------+   |   |   +---+   +-------+   |       +---+   +---+   |
|           |           |   |   |   |               |   |           |   |       |
+-----------------------+---+---+---+---------------+---+-----------+---+-------+

The following program produces the pentominos (and if desired the hexominos, septominos and so on) automatically, and then searches all solutions for arbitrary (not only rectangular) fields.

It is an ANSI-C program with an ascii-text output. So it should run on all operating systems and should be compilable (perhaps with some minimal adaptations) with all C-compilers. It is rather modularized and can be understood (I hope) even by beginners.

Here are some runtimes for pentominos on rectangular fields on a Pentium1 with 166MHz.

Field sizeRuntime
10x612min 38s
12x54min 7s
15x458s
20x63s

Download: pentominos.c.gz (5KB).


Homepage(german)     Computer stuff(german) by Michael Becker, 2/2002. Last modification 2/2002