Summary
The Polyform Puzzler project was begun to scratch an old itch. After a long delay, the project was finally launched and is now maturing nicely. Interested parties are welcome to join in!

Polyforms are shapes constructed by combining identical basic polygons (by their edges) or polyhedra (by their sides) in all possible ways. The most famous polyforms are the tetrominoes (which we've all seen in Tetris) and the pentominoes. There are 12 pentominoes, figures constructed from 5 squares:

The 12 pentominoes, with their common names.

Many sets of polyforms can combine to fill certain areas or volumes. These can be called "polyform puzzles" or "combinatoric dissection puzzles". For example, the pentominoes can fill a 6x10 rectangle:

One 6x10 pentominoes solution.

There are 2339 distinct ways to fit the pentominoes into a 6x10 rectangle, but it's not so easy to find one! Polyform Puzzler can find them all.

Other polyforms include polyiamonds (made from equilateral triangles), polyhexes (hexagons), polycubes, and polysticks (grid line segments). Many other polyforms are possible, and there are many web sites devoted to their exploration.

My interest in polyforms began when I discovered pentominoes, in Arthur C. Clarke's novel Imperial Earth, probably around the time I was 11 or 12 years old. I picked up a pentominoes puzzle ("Hexed", by Gabriel Toys) at a local hobby store and spent many hours discovering solutions.

In university, probably while avoiding legitimate study, I wrote the first implementation of a pentominoes-solving project, in Object Pascal. I developed an algorithm that solved the puzzle using brute force with some intelligence applied:

• Place each pentomino in every possible location.
• Confirm that the remaining empty spaces all have areas that are a multiple of 5 squares.
• For areas of exactly 5 squares, determine the piece that fits and confirm its availability.
• Check for bottlenecks that force a subset of the remaining space to accept only a single specific piece, and confirm its availability.

When I first learned Python, I reimplemented this as a practical learning exercise. I improved the algorithm a bit and got it to work pretty well, if not completely bug-free. It was a fun and interesting exercise, but the code was complicated and ran slow. (It didn't help that I only had a 66MHz computer at the time.)

I even went so far as to register the "puzzler" project on SourceForge, but didn't take it any further at that time. I had scratched my itch enough, and another itch became more persistent...

While writing the second implementation and learning Python I discovered Python docstrings and started looking around for auto-documentation systems to exploit them. I couldn't find anything that worked well for me, so I started scratching that itch, and eventually reStructuredText & Docutils were born. You could say that Polyform Puzzler spawned Docutils.

This summer I discovered a new approach for solving polyform puzzles, Donald Knuth's "Dancing Links Algorithm X" ("DLX") approach to the "exact cover" problem (described in the Polyform Puzzler FAQ, question 4.1). This approach was so different from what I'd done previously, and so obviously superior, that my old itch resurfaced. Polyform Puzzler is the result.

Since Polyform Puzzler launched on SourceForge in early August, it has been steadily maturing. The project code consists a set of front-end applications (solvers) for specific polyform puzzles and a Python library that does the heavy lifting (definitions of the polyforms, puzzles, and coordinate systems; and the DLX exact cover algorithm). New polyforms and new puzzles can easily be defined and added to the core.

Release 1 on August 8 featured 4 polyforms and 28 puzzles. The project currently features over 100 puzzles, configurations of 12 polyforms: pentominoes, solid pentominoes, pentacubes, tetracubes, soma cubes, hexiamonds, heptiamonds, tetrahexes, pentahexes, order 1-4 polyhexes, tetrasticks, and order 1-4 polysticks. We have SVG rendering for most polyforms, X3D models for 3-D polyforms (polycubes), and the capability to save session state (so a puzzle can be stopped and restarted). The project includes a gallery of puzzles & solutions; some examples below.

5x24 Pentahex Trapezoid

Heptiamonds Snowflake 2

Pentacubes Corner Crystal

In the short term I plan to add SVG rendering of polysticks (but the coordinate system code has to be reworked first) and then release version 2. In the long term, I hope to explore some ideas for as-yet-unexplored or minimally-explored polyforms, and perhaps work on a GUI. One pressing need is for greater speed; the exact_cover module should be rewritten as a C extension. Do I have to recondition my rusty C, or will some kind soul save me from the frustration?

I would welcome the participation of others interested in polyform puzzles. (I'd like to stop saying "I" so much and start saying "we" more ;-)

(Portions of this article were adapted from the Polyform Puzzler FAQ.)

Talk Back!

Have an opinion? Readers have already posted 6 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever David Goodger adds a new entry to his weblog, subscribe to his RSS feed.

Digg | del.icio.us | Reddit

About the Blogger