1.1   What is "Polyform Puzzler"?

Polyform Puzzler is a set of solvers for many polyform puzzles (like Pentominoes and Soma Cubes), and a software toolkit for exploring & solving polyform puzzles. It consists of a set of front-end applications for specific polyform puzzles and a Python library that does the heavy lifting. New polyforms and new puzzles can easily be defined and added to the core.

1.2   How did Polyform Puzzler begin?

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

In the summer of 2006 I discovered a new approach for solving polyform puzzles, Donald Knuth's "Dancing Links Algorithm X" ("DLX") approach to the "exact cover" problem, described below. 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.

1.3   Can others contribute?

Most definitely, yes! See the next question for how.

1.4   How can others contribute?

Python programmers

Please jump right in, there's a lot to do! Patches are welcome, as are new project members (see the next question).

Programmers who don't know Python

Have you considered learning Python? It's a great language, focused on programmer productivity. Python excels at the rapid creation of maintainable code. It's scalable. And it's fun. Give it a try!

There is one area where Python doesn't shine: raw speed. But that can be solved with extension modules written in C. The workhorse of the Polyform Puzzler project, the puzzler.exact_cover module, should be rewritten as an extension module in C for speed. See section 4, The Code, for an introduction.

Non-programmers

Have you considered learning to program? It's not as difficult as you think, and it can be loads of fun! Here are some guides for beginners to get you started.

Puzzlers

Use the project, and report on any issues you find. Run a puzzle marked "solutions incomplete" and send me the output. Let me know if you use and enjoy Polyform Puzzler!

Anyone

Do you enjoy Polyform Puzzler and want to say thanks? Is there a feature you'd like to see implemented? (Yes, I can be bribed!) Well, I love real-world, physical polyform puzzles too, and I'd love to receive some! Here's my wish list:

• Kadon's Super Deluxe Quintillions and Poly-4 Supplement
• Kadon's Iamond Hex, Iamond Ring, and Octiamond Ring
• Kadon's Hexnut Jr., Hexnut, and Hexnut II
• Solomon Golomb's Polyominoes (2nd ed.) (I have a copy of the first edition)

Plus, I have a wish list on Amazon.ca with a bunch of unrelated DVDs and books. My address is available on my résumé.

1.5   Can others join the project?

Most certainly, yes! All you need is a SourceForge account, and they're free. Just click the "Create Account" link on the project page or any SourceForge page.

2.1   What are "Polyforms"?

The word "polyform" can be defined from its parts:

poly-

more than one; many

form

shape

According to the Wikipedia definition,

a polyform is a plane figure constructed by joining together identical basic polygons

Regular polygons which tile the plane (fill, without gaps or overlap; a tessellation) are the most satisfying basic polygons for polyform puzzles, and there are three: the equilateral triangle, the square, and the hexagon. Other polygons can be used though. With a given polygon, the set of polyforms of order N is defined by constructing all possible combinations of N copies of that polygon, joined edge to edge, without overlapping. Duplicates (from rotation or reflection) are typically ignored, although some puzzles explicitly treat reflections separately ("one-sided").

For example, 5 squares can be combined in 12 different ways, resulting in the "pentominoes":

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 6×10 pentominoes solution.

There are 2339 distinct ways to fit the pentominoes into a 6x10 rectangle. Polyform Puzzler can find them all.

The definition of polyforms above can be generalized to include solids (polyhedra) joined face to face. Regular (Platonic) solids that fill space are the most satisfying, but there is only one Platonic solid that fills space: the cube. Tetrahedra and octahedra together can fill space though. In addition, the truncated octahedron (a semi-regular, Archimedian solid) and the rhombic dodecahedron can each individually fill space, as can other, less regular polyhedra.

The polyform definition can also be extended to include other forms, like line segments of a grid (polysticks). The sky's the limit!

2.2   What polyforms are there?

There are many possible families of polyforms, with new ones being invented all the time. Polyform Puzzler only deals with a limited number of polyforms; in my opinion the most aesthetically pleasing ones. Polyform families are given descriptive names:

• Square-based polyforms are named "polyominoes" (from a "domino", which is two squares joined): monomino, domino, tromino, tetromino, pentomino, hexomino, etc.

  The tetrominoes are famous for their role in the videogame "Tetris". The 12 pentominoes are probably the most well-known polyform, due to their versatility and the large variety of non-trivial puzzles they form.

  

  3×20 Pentominoes (2 solutions; can you see the other one?)

  

  3×30 One-Sided Pentominoes (46 solutions)

• Substituting a 3D cube for each 2D square in polyominoes results in "solid polyominoes" or "planar polycubes".

  

  3×4×5 Solid Pentominoes (3940 solutions)

• Polyforms based on cubes extending into 3 (or more!) dimensions are called "polycubes". The polycubes that are flat (only one cube thick) are known as "planar polycubes" or "solid polyominoes".

  

  2×2×8 tetracubes (224 solutions)

  Soma Cubes are a well-known group of 7 polycubes (6 tetracubes and 1 tricube): all the non-convex (non-box-like) 3-dimensional polycubes up to order 4 (because with 5 cubes, we'd need 4 dimensions!).

  

  3×3×3 Soma Cubes (240 solutions)

• Polyforms based on equilateral triangles are named "polyiamonds" (from the "diamond", which is two triangles joined).

  

  4×10 Hexiamond Elongated Hexagon (856 solutions)

• Polyforms based on regular hexagons are named "polyhexes" (there's no clever etymology here).

  

  5×7 Tetrahex "Coin" (4 solutions)

• Polyforms based on unit line segments joined end-to-end on a square grid are called "polysticks" [1] (a.k.a. "polyedges" or "polypleura"). The shapes formed from matchsticks joined together end-to-end at 90° angles are polysticks. Polysticks are related to polyominoes: polysticks can be thought of as paths joining the centers of the squares of polyominoes.

  

  Polysticks of Order 1-4 in a 3×7 Diamond Lattice

2.3   How many of each type of polyform are there?

Hyperlinks in parentheses are to the relevant entries in The On-Line Encyclopedia of Integer Sequences.

• Polyominoes (A000105, A000988):

  Squares	Name	Polyominoes	One-Sided
  1	monomino	1	1
  2	domino	1	1
  3	tromino	2	2
  4	tetromino	5	7
  5	pentomino	12	18
  6	hexomino	35	60
  7	heptomino	108	196

  This table also applies to solid polyominoes (planar polycubes).

• Polyiamonds (A000577, A006534):

  Triangles	Name	Polyiamonds	One-Sided
  1	moniamond	1	1
  2	diamond	1	1
  3	triamond	1	1
  4	tetriamond	3	4
  5	pentiamond	4	6
  6	hexiamond	12	19
  7	heptiamond	24	43
  8	octiamond	66	120

• Polyhexes (A000228, A006535):

  Hexagons	Name	Polyhexes	One-Sided
  1	monohex	1	1
  2	dihex	1	1
  3	trihex	3	3
  4	tetrahex	7	10
  5	pentahex	22	33
  6	hexahex	82 [*]	147

  [*]	One hexahex contains a central hole (1 hexagon). It is used for one of the "o" letters in this project's logo.

• Polycubes (A000162):

  Cubes	Name	Polycubes
  1	monocube	1
  2	dicube	1
  3	tricube	2
  4	tetracube	8
  5	pentacube	29
  6	hexacube	166

• Polysticks (a.k.a. "polyedges"; A019988):

  Sticks	Name	Polysticks	One-Sided
  1	monostick	1	1
  2	distick	2	2
  3	tristick	5	7
  4	tetrastick	16	25
  5	pentastick	55	99

2.4   Where can I find more information about polyforms?

There are many web sites with polyform information. If you're looking for specific information, a search engine is your best bet. Here are a few good places to start:

• Wikipedia
• MathWorld
• The Poly Pages
• Vicher's Puzzle Pages
• MathPuzzle.com
• The Geometry Junkyard
• Pentamini pentaminos pentominoes
• More about polyforms (Kadon Enterprises)
• More about Polyominoes and Polycubes (Kadon Enterprises)
• Game and Puzzle Sites (Kadon Enterprises)

2.5   Where can I find physical polyform puzzles?

For a wide variety via mail order, I highly recommend Kadon Enterprises (see my wish list).

I also recommend doing research on the web, then checking out your local toy, game, and puzzle specialty stores. If they don't stock what you want, ask them to get it for you! Here are some sources that I know of:

• The 21 polyominoes of order 1-5 are used as the playing pieces in the "Blokus" board game.
• Solid pentominoes are commonly available in the "Pocket Play" series by Shoptaugh Games (distributed in Canada and elsewhere by Family Games).
• Soma Cubes are sold under the name "Block By Block" by ThinkFun.
• The 22 polyiamonds of order 1-6 are used as the playing pieces in the "Blokus Trigon" board game.
• In Japan, many polyform puzzles are available from Tenyo.

3.1   What polyform puzzles are supported?

Many polyomino, polyiamond, polyhex, polycube, and polystick puzzles are supported. For a full list, see the Puzzles & Solutions document. More polyforms are to come:

• other polyominoes
• other polycubes
• other polyiamonds
• other polyhexes
• other polysticks
• and other polyforms!

See the to do list for details.

3.2   How should the solution files be interpreted?

The solution files are text files that all follow a common pattern. The first line states the puzzle matrix class (from the puzzler.puzzles module) being solved:

Solving Pentominoes6x10Matrix:

Some puzzles are split up into several matrices. After all the solutions for one matrix are exhausted, the name of the next matrix will be given.

Each solution record contains three parts. First, the solution header with the solution number:

solution 1:

The second part of the solution record lists the solution coordinates, one piece per line, with the piece name last:

1,1 2,0 2,1 2,2 3,1 X
0,0 0,1 0,2 0,3 1,0 L
3,0 4,0 4,1 4,2 5,1 F
5,0 6,0 6,1 6,2 7,0 T
1,2 1,3 2,3 3,2 3,3 U
0,4 0,5 1,4 1,5 2,4 P
2,5 3,5 4,5 5,5 6,5 I
5,2 5,3 6,3 7,3 7,4 Z
3,4 4,3 4,4 5,4 6,4 Y
7,5 8,5 9,3 9,4 9,5 V
7,1 7,2 8,0 8,1 9,0 W
8,2 8,3 8,4 9,1 9,2 N

In some puzzles, like the 6x6 tetrasticks, one or more pieces are omitted from each solution. Such omitted pieces are listed with "!" in place of the coordinates list:

! H

If there are omitted pieces, a notice is prefixed to the visual representation:

(H omitted)

The third part of the solution record is a visual representation of the solution:

P P I I I I I V V V
P P P Y Y Y Y Z N V
L U U U Y Z Z Z N V
L U X U F Z T W N N
L X X X F F T W W N
L L X F F T T T W W

Finally, the number of solutions, the number of searches (software operations executed), and the duration (time taken to complete the execution) are listed:

2339 solutions, 906813 searches, duration 0:19:10.133000

3.3   How should polyomino solution files be interpreted?

Polyominoes use a 2-dimensional X,Y cartesian coordinate system.

The visual representation consists of piece names (letters) in a 2-D grid. Imagine each letter as a square, with adjacent like-labelled squares joined:

N Z I I I I I U U U
N Z Z Z P P P U W U
N N T Z X P P W W L
V N T X X X W W F L
V T T T X Y F F F L
V V V Y Y Y Y F L L

3.4   How should polycube solution files be interpreted?

Polycubes (solid pentominoes, Soma cubes) use a 3-dimensional X,Y,Z cartesian coordinate system.

The visual representation consists of piece names (letters) in multiple layers, each a 2-D slice of a 3-D space. Imagine the layers stacked up from left to right, with each letter as a cube, with adjacent like-labelled cubes joined:

U V V V N    U W T T T    U W Z L Y
U W Z V N    X W Z T Y    U F Z L Y
X W Z V N    X P P T N    X F F L Y
I I I I I    X P P P N    F F L L Y

Some polycube puzzles, like the solid pentomino ring puzzles, are equivalent to a 2-dimensional puzzle folded into 3 dimensions. These puzzles' visual representations consist of the view from each side of the solution, with corners duplicated between adjacent sides:

U U V    V Z Y Y Y Y W T F    F L L    U X P P P L L L L
X U V    V Z Z Z Y W W T F    F F F    X X X P P N N N F
U U V    V V V Z W W T T T    T F N    U X I I I I I N N

In the solution to the 3x3x9 solid pentomino ring puzzle above, the left wall is shown first, then the front wall, then the right wall, then the back wall. The back wall is shown with the same orientation as the front wall.

3.5   How should polyhex solution files be interpreted?

Polyhexes use a 2-dimensional X,Y, skewed cartesian coordinate system. The X and Y axes are 60° apart instead of 90°.

The visual representation is an ASCII-art drawing of the solution, with the Y-axis vertical and the X-axis sloping up:

                   __
                __/  \
             __/  \  /
          __/   __/  \
       __/     /   __/
    __/  \__   \  /  \
 __/   __   \__/  \  /
/  \  /  \__/  \__/  \
\  /  \__    __/   __/
/  \__/  \  /   __/
\  /     /  \__/
/  \     \__/
\  /   __/
/  \__/
\__/

3.6   How should polyiamond solution files be interpreted?

Polyiamonds use a pseudo-3-dimensional X,Y,Z, skewed cartesian coordinate system. The X and Y axes are 60° apart instead of 90°, and the Z dimension is used to represent the orientation of triangles:

           ____
    /\     \  /
z=0/__\  z=1\/

The visual representation is an ASCII-art drawing of the solution, with the X-axis horizontal and the Y-axis sloping to the right:

        ____________________________________
       /   /           /    \      /       /
      /   /___________/   ___\    /       /
     /       /    \      /   /    \  /\  /
    /_______/      \____/   /______\/  \/
   /       /\      /   /\       \      /
  /   ____/  \____/   /  \_______\    /
 /   /        \       \          /   /
/___/__________\_______\________/___/

3.7   How should polystick solution files be interpreted?

Polysticks use a pseudo-3-dimensional X,Y,Z cartesian coordinate system, but the line segments of the grid are significant, not the squares. The Z dimension is used to represent the direction of line segments: 0=horizontal, 1=vertical. Horizontal line segments "x,y,0" start at (x,y) and end at (x+1,y), one unit to the right. Vertical line segments "x,y,1" start at (x,y) and end at (x,y+1), one unit up. (The Z dimension corresponds to the index of the dimension that increases.) Internal intersections (where grid lines cross) are also shown, in the form "x,yi", but these can be ignored.

The visual representation consists of piece names (letters) in an ASCII-art drawing of the 2-D grid. Imagine each line segment with adjacent like-labelled segments joined:

 -R-- -T-- -T-- -R*-
Y    R    T    R    Y
*    |    |    *    |
 -Y*- -R-- -R*- -Y--
Y    R    T    R    Y
*    |    |    *    |
 -H-- -H-- -H*- -H*-
Y    H    X    H    Y
*    |    |    *    |
 -H-- -X-- -X-- -H*-
F    F    X    F    F
|    |    |    *    *
 -F-- -F-- -F*- -F*-

The solution above is from the 5x5 welded one-sided tetrasticks puzzle. Asterisks ("*") indicate flipped pieces.

4.1   How are the polyform puzzles solved?

Polyform Puzzler works by reducing puzzles into "exact cover" problems. Briefly, to solve an exact cover problem, given a matrix of 0s and 1s, we must find a set of rows which, when combined, contain exactly one 1 in each column. To find every solution we must find all such sets of rows.

We construct a two-dimensional matrix with named columns. The column names consist of the puzzle piece names, then the coordinates of the solution space. For example, in a puzzle with three pieces to be placed in a 3x3 grid, we'd have 12 columns:

A  B  C    0,0  1,0  2,0    0,1  1,1  2,1    0,2  1,2  2,2

We determine every possible position of each puzzle piece in the puzzle, and construct one row for each position. Starting with a row of 0s, put a 1 in the column for the puzzle piece name and in each column corresponding to the position of the puzzle piece. For example, puzzle piece A covering coordinates (0,0), (0,1), and (1,1) would create this row in the matrix:

1  0  0    1  0  0    1  1  0    0  0  0

Once all the rows have been constructed (there may be many), the solutions can be found by identifying sets of rows that, combined, have exactly one 1 in each column. For example, this is one such solution:

1  0  0    1  0  0    1  1  0    0  0  0
0  1  0    0  1  1    0  0  1    0  0  0
0  0  1    0  0  0    0  0  0    1  1  1

The puzzler.exact_cover module implements Donald E. Knuth's Dancing Links approach to his Algorithm X ("DLX"). For a complete description of DLX, see Knuth's paper (compressed PostScript original or PDF version).