The pentomino problem consists of a set of twelve shapes, each consisting of
five variously-arranged unit squares. For example, one shape is a rectangle of
length five units and width one unit. The object is to arrange all twelve
shapes into a rectangle. The pentomino program, "pentomin.exe", uses a brute
force method to find every way in which the pentominos may be arranged to form
a rectangle, being careful to avoid rotations and reflections of previously
identified solutions.
Below is running a JavaScript and SVG2
version of the program.
This JavaScript version of the program runs slowly,
intentionally, so as not to consume all your CPU power, but it should give you
some idea of what it's about. Once it exhausts all solutions for the 3x20
configuration, it will advance, in turn (if you are sufficiently patient) to
the 4x15, 5x12, and 6x10 configurations. If you are not sufficiently patient,
you can advance, manually, to the other configurations by clicking on the
rectangle. It should not take you long, watching it, to see improvements that
can be made to the algorithm.
This JavaScript program employs SVG2
to present the arrangement of pentominoes.
The executable version of this program, which was written in "C" quite
differently to the JavaScript
version above, is available for you to
download and save or run or to
download the zip file that includes
the Pentomino program (111.3kB), then extract and run
“pentomin.exe”.
The file, “pentomin.exe”, is a Microsoft Windows Console
application, so, if, after downloading the executable, you double-click on
“pentomin.exe”, it will open an MS-DOS window and run. If you allow
it to run to completion, which might takes days, depending upon your computer's
speed, it will produce a listing of all solutions in the file
“PENTOMIN.RTF”.
This was a problem set for my daughter (and her class mates) when she
started high school. She attempted to find solutions using cut-out pieces of
paper, which would never stay where they were placed, making the exercise
rather frustrating. Instead of cutting new peices out of cardboard, as a
sensible person would have done, I decided to write a program to do it
instead.
The other diversion included in this ZIP file is the
“Betagraph” demonstration.
