.. -*- coding: utf-8 -*-
=====================================================
Polyform Puzzler, New Polyforms, and Recent Results
=====================================================
----------------------------------------------------------------
A Talk from G4G10: The 10th Gathering for Gardner (2012-03-31)
----------------------------------------------------------------
:Author: David Goodger
:Date: $Date: 2016-08-22 07:57:53 -0500 (Mon, 22 Aug 2016) $
:Revision: $Revision: 629 $
:Web site: http://puzzler.sourceforge.net/
:Copyright: © 1998-2015 by David J. Goodger
:License: `GPL 2 <../COPYING.html>`__
.. image:: images/puzzler.png
:align: center
.. sidebar:: Also see:
* `X’s from G4G10: Gathering for Gardner 10 `_
* `Polyform Puzzler: Puzzles & Solutions `_
* `Polyform Puzzler FAQ `_
Off-site:
* `My account of G4G10 (blog article)
`_
.. contents::
I presented this as a whirlwind 5 minute introduction to the Polyform
Puzzler software project at the `10th Gathering for Gardner (G4G10)`_,
Atlanta, Georgia, USA, 2012-03-31. This version is updated and
contains some extra content that had to be omitted from the talk for
time.
.. _10th Gathering for Gardner (G4G10): http://gathering4gardner.org/
(To get a feel for what the Gatherings are all about `watch this
episode of “The Nature of Things” about Martin Gardner with footage
from Gathering for Gardner 2 in 1996 `__.)
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
=======
.. image:: images/g4g10/imperial-earth.jpg
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.
.. list-table::
:class: borderless
* - .. figure:: images/g4g10/martin-gardner.jpg
Martin Gardner
- .. figure:: images/g4g10/solomon-golomb.jpg
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
==============
.. image:: images/g4g10/pentominoes.png
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
====================
.. image:: images/g4g10/dancing-links.png
.. image:: images/g4g10/matrix.png
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!
========
.. image:: images/ominoes/pentominoes-6x10.png
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.
.. figure:: images/iamonds/heptiamonds-snowflake-2.png
heptiamonds snowflake
.. figure:: images/hexes/pentahexes-triangle-1.png
pentahexes triangle
.. figure:: images/cubes/solid-pentominoes-3x4x5.png
solid pentominoes 3×4×5
.. figure:: images/sticks/one-sided-tetrasticks-5x5-diamond-lattice.png
one-sided tetrasticks 5×5 diamond lattice
.. figure:: images/g4g10/sudoku.png
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.
.. list-table::
:class: borderless
* - .. image:: images/cubes/pentacubes-corner-crystal.png
- .. figure:: images/cubes/pentacubes-corner-crystal-small.jpg
:target: images/cubes/pentacubes-corner-crystal.jpg
Built with `Kadon's Super Deluxe Quintillions`_.
Click for the full-size image.
.. _Kadon's Super Deluxe Quintillions:
http://gamepuzzles.com/polycube.htm#SQd
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?
================
.. image:: images/g4g10/dog-scratching.jpg
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
=========
.. image:: images/trigs/one-sided-tritrigs-hex-4x1.png
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.
.. image:: images/trigs/tritrigs-heart-1.png
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.
.. image:: images/g4g10/one-sided-tritrigs-chevron-8x1.png
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
=========
.. image:: images/twigs/hexatwigs-triangle.png
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.]*
.. image:: images/twigs/pentatwigs-trefoil.png
*[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:
.. image:: images/ominoes/polyominoes-2345-x-1.png
The one-sided polyiamonds of order 1 through 5 (looks a bit like a
“Primrose X”):
.. image:: images/iamonds/one-sided-polyiamonds-12345-x-1.png
The one-sided polyhexes of order 1 through 4:
.. image:: images/hexes/one-sided-polyhexes-1234-x-1.png
The polycubes of order 1 through 5 (featuring a script “x” on the
face):
.. list-table::
:class: borderless
* - .. image:: images/cubes/polycubes-12345-x-5.png
- .. figure:: images/cubes/polycubes-12345-x-5-small.jpg
:target: images/cubes/polycubes-12345-x-5.jpg
Built with `Kadon's Super Deluxe Quintillions`_ and `Poly-4
Supplement`_. Click for the full-size image.
.. _Poly-4 Supplement: http://www.gamepuzzles.com/poly4.htm
The one-sided tetrasticks:
.. image:: images/sticks/one-sided-tetrasticks-x-1.png
The hexatwigs:
.. image:: images/twigs/hexatwigs-x-6.png
And finally, the one-sided polytrigs of order 1 through 3:
.. image:: images/trigs/one-sided-polytrigs-123-x-1.png
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.
| David Goodger
| goodger@python.org