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!
Advertisement
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 ;-)
I too recently discovered Knuth's algorithm for this. Having written, over the years, several versions of this along the lines of the "brute force" approach you describe, I was (briefly) all geared up and ready to rewrite your exact_cover routine in C or at least C++.
As a long term CVS user, I was also enticed by the opportunity to briefly dip into SVN. CVS is getting awfully long in the tooth and, although it still works well for us, it is time to move on.
However, my brief burst of enthusiasm has been dampened by the apparent impossibility of getting a simple SVN client installed on any flavour of Windows box. The culmination of my attempt to achieve this was my discovery on the SVN mailing lists of the following exchange, apparently (at least partly) from fairly central people:
kfogel@collab.net wrote:
>olczyk@interaccess.com writes: > > >>But I don't see a way of using that script to generate project files >>that are client only, and the normal generatied scripts are to >>intertwined with server builds. >> >> > >I'm not competent to describe how to do a client-only build on >Windows. Can anyone else say how to do it? A patch to INSTALL would >be ideal; if not, a prose description on this list would still help. > > There is no client-only build on Windows.
Arrrggghh...
I'm not going to go through an entire server-side install of all this stuff just to download the source code for one module, especially after I read this:
The instructions really aren't that bad, but man are there ever a lot of little extra pieces you have to find, download, and get working! In some cases the libs for the libs need libs. Because of this you eventually find yourself nested three deep in instructions for instructions for instructions. %-P
I'm sure all the libs are useful, and it makes sense to use their downloads and their instructions rather than try to include them and rewrite the instructions yourself (and have to redo them every time they change). So I don't know the solution to this issue. Most folks should probably just download a prebuilt binary client and not have to worry about it. Perhaps those of us who want to code against the subversion API should be smart enough to figure out how to do this, but it sure was a pain.
So my question is, am I missing how easy it is to install a simple SVN client on an XP box? Isn't there some .msi file which will both install and run the client with a single double-click?
Otherwise, is there some other (non-SVN) way I can access the code? More to the point, how might I then commit anything I might achieve?
I hasten to add that I apologize for sounding like I'm bashing your code when all the problems (so far) are entirely unrelated to what you've written. I look forward to being able to change your "I" into "us", but I'm either going to have to get a lot more committed to SVN, or I'll have to find some other work-around.
I've discovered, as I imagine everyone but me knows, that SourceForge makes modules in SVN repositories available in text format as a standard option. Funny, I've been using SourceForge for years and never knew that.
I've downloaded the various components and will start playing with them. I know little about Python although it's installed on lots of the machines I use -- ironically because it's required for WinCVS, the very basic CVS client I tend to use. However, now is as good a time as any to learn.
It's not yet clear to me how to invoke a C module in Python in a platform-independent way (assuming it's possible at all). Are you able to provide a link / reference / example on how to do this?
Even more ironically, I only read your bio after writing the previous post. I too am near Montreal (well, if you count the Plateau as "near"), and I too lived in Japan for some time. How strange...
> So my question is, am I missing how easy it is to install > a simple SVN client on an XP box? Isn't there some .msi > file which will both install and run the client with a > single double-click?
TortoiseSVN is not only an easy installation of SVN on Windows, it also provides a plugin to the Windows Explorer file browser, adding SVN functionality to the right-click menu.
> It's not yet clear to me how to invoke a C module in > Python in a platform-independent way (assuming it's > possible at all). Are you able to provide a link / > reference / example on how to do this?
> Even more ironically, I only read your bio after writing > the previous post. I too am near Montreal (well, if you > count the Plateau as "near"), and I too lived in Japan for > some time. How strange...
Plateau Mont-Royal? That's closer than me! I live in Pincourt, but I work downtown.
Cool game! If you go to http://www.tamsa.org and click on their Pentominoes link, you can play a free version of the game with the 12 pentominoes figures on a 6 X 10 board (it's not java).
Previous Topic
