The Artima Developer Community
Sponsored Link

Weblogs Forum
A Puzzling Divertimento

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

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
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 4:14 PM
Reply to this message Reply
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:

http://puzzler.sf.net/docs/images/ominoes/pentominoes.png

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:

http://puzzler.sf.net/docs/images/ominoes/pentominoes6x10.png

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.

http://puzzler.sourceforge.net/docs/images/hexes/pentahexes-5x24-trapezoid.png

5x24 Pentahex Trapezoid

http://puzzler.sf.net/docs/images/iamonds/heptiamonds-snowflake-2.png

Heptiamonds Snowflake 2

http://puzzler.sf.net/docs/images/cubes/pentacubes-corner-crystal.png

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


Jeff Heon

Posts: 40
Nickname: jfheon
Registered: Feb, 2005

Re: A Puzzling Divertimento Posted: Sep 28, 2006 9:13 PM
Reply to this message Reply
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 10:13 PM
Reply to this message Reply
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.

PK

Paul Kroitor

Posts: 2
Nickname: alatar
Registered: Mar, 2008

Re: A Puzzling Divertimento Posted: Mar 25, 2008 10:46 PM
Reply to this message Reply
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 9:28 AM
Reply to this message Reply
> 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 9:39 AM
Reply to this message Reply
> 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/

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

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 11:03 AM
Reply to this message Reply
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
Topic: A Puzzling Divertimento Previous Topic   Next Topic Topic: Java going bigger, bigger, bigger


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us