Weblogs Forum
A Puzzling Divertimento

6 replies on 1 page. Most recent reply: Sep 23, 2006 1:14 PM by David Goodger

 Previous Topic Next Topic
 Flat View: This topic has 6 replies on 1 page
 David Goodger Posts: 48 Nickname: goodger Registered: Apr, 2004
A Puzzling Divertimento (View in Weblogs)
Posted: Sep 23, 2006 1:14 PM
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:

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:

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.

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 ;-)

 Jeff Heon Posts: 40 Nickname: jfheon Registered: Feb, 2005
Re: A Puzzling Divertimento Posted: Sep 28, 2006 6:13 PM
When I saw your blog entry, I thought at once of a board game catching on around where I live.

It's called Blokus and it's using the 12 pentominoes.

If you go through the hassle of registering, you can play a free java online version of it.

http://www.blokus.com/

 Paul Kroitor Posts: 2 Nickname: alatar Registered: Mar, 2008
Re: A Puzzling Divertimento Posted: Mar 25, 2008 7:13 PM
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. %-PI'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.

PK

 Paul Kroitor Posts: 2 Nickname: alatar Registered: Mar, 2008
Re: A Puzzling Divertimento Posted: Mar 25, 2008 7:46 PM
Mea culpa.

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...

PK

 David Goodger Posts: 48 Nickname: goodger Registered: Apr, 2004
Re: A Puzzling Divertimento Posted: Mar 26, 2008 6:28 AM
> 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?

Yes, there is: http://tortoisesvn.tigris.org/

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.

 David Goodger Posts: 48 Nickname: goodger Registered: Apr, 2004
Re: A Puzzling Divertimento Posted: Mar 26, 2008 6:39 AM
> 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?

I suggest the "Extending and Embedding" and "Python/C API" manuals from
http://www.python.org/doc/current/

> 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.

I actually did a talk on Polyform Puzzler at the Montreal Python meeting on 7 February (http://www.barcampmontreal.org/wiki/MontrealPython1 ; photo: http://flickr.com/photos/montrealtechwatch/2251096254/). The next meeting will be 10 April (http://montrealpython.org/?p=20).

I suggest that we take this discussion to the Polyform Puzzler mailing list, https://lists.sourceforge.net/lists/listinfo/puzzler-users
(and if that doesn't work, mail me directly: goodger (at) python dot org).

 Steve Baker Posts: 1 Nickname: venzo Registered: Jun, 2008
Re: A Puzzling Divertimento Posted: Jun 27, 2008 8:03 AM
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).

 Flat View: This topic has 6 replies on 1 page
 Previous Topic Next Topic