Introduction

This is my first time at a Gathering for Gardner. I’m grateful and honoured to have been invited. In order to justify my presence here, I’d like to tell you about my little project.

Polyform Puzzler is a Free Software project, first published on the Internet in 2006. It currently supports 7 different families of polyforms, several orders of each, and solves several hundred individual puzzles. It generates attractive graphics for puzzle solutions, and even produces 3-D output.

History

I first discovered Pentominoes in Arthur C. Clarke’s novel Imperial Earth, probably around the time I was 11 or 12 years old. I bought a set of plastic pentominoes at a local hobby store and spent many happy hours discovering solutions.

The novel’s afterword led me to the work of two of the great thinkers in the field, Martin Gardner and Solomon W. Golomb.

Martin Gardner

Solomon W. Golomb

[Omitted from the talk due to time constraints:]

As a teenager I read some of Martin Gardner’s books, and later, thanks to my university’s library archives, I was able to read many of his original Scientific American articles. What a font of knowledge! The world is a richer place for Martin Gardner having been in it.

Eventually I got my hands on a copy of Golomb’s Polyominoes, which was hard to find in the pre-Amazon.com days. I now have both editions. I was delighted to have been able to meet Professor Golomb at G4G10.

Early Attempts

As a teenager I became interested in computer programming so I naturally tried to write a pentominoes solver. I tried to get the computer to solve puzzles the same way I did – but it didn’t work well. It was the wrong approach. It’s not just that computers don’t think the same way people do, it’s that computers don’t think at all. They’re just fast calculators.

10 or 12 years later I re-implemented my pentominoes solver as a toy project to learn the Python programming language. It worked, but it was incredibly slow, and I didn’t take it any further.

Knuth Opened My Eyes

Then in the summer of 2006 I learned of a new approach for solving polyform puzzles, in Donald Knuth’s “Dancing Links” paper. This approach re-frames puzzles as “exact cover” problems, represented by a sparse matrix of 0s and 1s and solvable by Knuth’s “Algorithm X”. Much more suited to solution by computer. My old itch resurfaced.

Success!

Using the Python programming language I implemented an Exact Cover problem solver in a general way, and Polyform Puzzler started producing results. Success!

Familiar Polyforms

I implemented the rest of the familiar regular polygon and polyhedron unit shape polyforms: the polyiamonds, the polyhexes, and the polycubes. Prof. Knuth’s paper also discussed polysticks, which piqued my interest so I implemented those too. And since Sudoku puzzles can also be framed as exact cover problems, I also implemented a Sudoku solver.

heptiamonds snowflake

pentahexes triangle

solid pentominoes 3×4×5

one-sided tetrasticks 5×5 diamond lattice

sudoku

Correspondence

Polyform Puzzler went live on the Internet in 2006, and since then several puzzle enthusiasts around the world have shared their ideas with me.

Built with Kadon's Super Deluxe Quintillions. Click for the full-size image.

For example, Nick Maeder of New Zealand devised the pentacubes puzzle above, “corner crystal”, around 1984. He had tried to solve it manually off and on for 22 years, coming within one piece of a solution. Polyform Puzzler was able to find a solution after only a few hours of computer time – now down to just a few minutes, with faster computers and a much more efficient core solving engine.

Itch: Scratched?

Finally I had implemented all the existing polyforms that interested me – I’m biased toward regular unit shapes & symmetrical puzzles. I had scratched my own itch, and I didn’t give the project much attention for a while.

But does this kind of itch ever really go away? Apparently not. About a year ago I started experiencing flare-ups, so I devised some new polyforms to explore.

Polytrigs

First I implemented triangular-grid polysticks, or “polytrigs” as I called them. I found only a few references; this form doesn’t seem to have been explored much before this. [Above is the one-sided tritrigs 4×1 semi-regular hexagon.]

Recently I heard from Les Shader, who shared the results of his unpublished work on triangular-grid polysticks from the early 1990s. Below is his “tritrigs heart” design. I have Les to thank for my invitation to this Gathering.

Polytrigs Challenge

The polytrigs were a challenge because the pieces can overlap if we’re not careful. With physical puzzles, it’s not a problem: either the piece fits, or it doesn’t. With virtual polysticks, we have to keep track of the intersections.

Square-grid polysticks have simple intersections: either an intersection is occupied or not.

The triangular-grid polysticks have more complex intersections: multiple pieces can occupy an intersection simultaneously, as you can see in two different ways above. I had to devise a way to keep track of which pieces can and can’t use an intersection together.

This is at least part the subject of the paper I’m writing as my contribution to the gift exchange book.

Polytwigs

After polytrigs, I considered the hexagonal-grid polysticks, which I named “polytwigs” (because individually the pieces look like little branching twigs). They were much easier to implement than the triangular-grid polytrigs, lacking any intersection constraints at all. [Above is the hexatwigs triangle.]

The hexagonal-grid polytwigs are actually a restricted subset of the triangular-grid polytrigs (both sets will fit on the triangular grid).

I couldn’t find any prior mention of hexagonal-grid polysticks. But it turns out that even they have been explored. I received email from Colin F. Brown, a puzzle enthusiast from England, who shared his work from the 1970s on hexagonal-grid polysticks, including the quasi-connected form. In fact, he did some very early work on square-, triangular-, and hexagonal-grid polysticks in general. Unfortunately he never published before now.

[Below is Mr. Brown’s pentatwigs trefoil design. Note that it is composed of 3 congruent shapes.]

[Omitted from the talk due to time constraints:]

Mr. Brown was also greatly influenced by Martin Gardner’s Scientific American columns and books. He eloquently wrote,

Martin Gardner served up the starter, the main course and the dessert, and, ten times out of ten, something to nibble at later. For me, he will always be the father of recreational mathematics.

Evolving Algorithms

[Omitted from the talk due to time constraints:]

The great thing about the Python programming language is that it makes turning ideas into working computer programs easy and quick. Python’s only downside is that the resulting programs are slow to run, which really hurts when solving larger puzzles. But last month I discovered an Exact Cover solver backend written as a C extension to Python, which I’ve been adapting to Polyform Puzzler, soon to be published. This means that Polyform Puzzler will solve puzzles at lightning speed! It will be the best of both worlds.

X!

In preparation for this 10th Gathering, I designed and solved some new puzzles that match the “X” theme. All of these and more are now available on the Polyform Puzzler site.

Here’s an X formed from the polyominoes of order 2 through 5:

The one-sided polyiamonds of order 1 through 5 (looks a bit like a “Primrose X”):

The one-sided polyhexes of order 1 through 4:

The polycubes of order 1 through 5 (featuring a script “x” on the face):

Built with Kadon's Super Deluxe Quintillions and Poly-4 Supplement. Click for the full-size image.

The one-sided tetrasticks:

The hexatwigs:

And finally, the one-sided polytrigs of order 1 through 3:

Conclusion

I would love to have more correspondents! If you have polyform puzzle ideas you’d like to share with the world, please write to me.

Thanks for reading about one of my obsessions.