How to Extend Polyform Puzzler

Author: David Goodger <>
Date: 2015-02-24
Revision: 600
Web site:
Copyright: © 1998-2015 by David J. Goodger
License:GPL 2


This document is incomplete, a work in progress. If you have any questions, please ask on the mailing list (subscribe here).



This document assumes some (but not much) familiarity with programming and the Python programming language. This is not a Python tutorial, but it is written for beginning Python programmers. You should be able to follow these instructions after completing a tutorial.

The Python web site contains lists of tutorials for those new to programming, as well as for programmers new to Python.

Experienced Python developers should just skim the text & code examples for technical API details.

The Parts of a Puzzle

Polyform Puzzler puzzles conceptually consist of three parts:

  1. The coordinate system.
  2. The polyform definition.
  3. The puzzle definition.

Existing coordinate systems (part 1) are implemented in the puzzler/ module. Polyform definitions and puzzle definitions are implemented in modules in the puzzler/puzzles/ directory. Polyform definitions are classes, subclasses of the puzzler.puzzles.Puzzle class. Puzzle definitions are also classes, subclasses of the polyform definition classes.

If the polyform for your puzzle is already defined, just add a new puzzle definition.

If the polyform for your puzzle is closely related to an existing polyform, you may be able to modify the existing polyform.

If the polyform for your puzzle is new, but the coordinate system for that polyform is already implemented, you'll have to define a new polyform.

If the polyform for your puzzle requires a coordinate system that is not yet implemented, you'll have to define a new one.

A Module For Your Puzzle

The first thing you will need is a fresh, clean text file. Call it whatever you like, although the file name should end with ".py" for simplicitly, defining a Python source module. We'll use "" for these instructions (using underscores instead of hyphens in module names is helpful in testing and debugging).

It's best not to edit the Polyform Puzzler files directly. If you do, you may lose your additions when you re-install Polyform Puzzler. By putting your puzzle definition code in a separate module, you isolate it from the rest of the Polyform Puzzler code. You're welcome to send your code for addition to the project though. Write to the Polyform Puzzler users mailing list.

Use a text editor, not a word processor, to create this file (word processors create formatted documents; we want a plain text file). A text editor with support for Python code would be helpful, but is not necessary.


This is where your puzzle's unique defining characteristics go. The possiblilities are described in detail in later sections. At the very least, you'll need a class definition for your puzzle. In this document we'll call your puzzle class "MyPuzzle".

Solve It

When you have finished defining your puzzle, you'll be ready for Polyform Puzzler to solve it. In a shell or DOS box, enter the following command:


Define a New Puzzle Using an Existing Polyform

For this example, we'll implement a 3x21 pentomino rectangle with three holes:


Bounding Box

The first thing to define is the overall size, or maximum dimensions, or bounding box of the puzzle solution. In other words, how wide and how high of a box can the puzzle fit into? Pentominoes puzzles use ordinary 2-dimensional (X, Y) Cartesian coordinates. Other puzzles use 3-dimensional (X, Y, Z) Cartesian coordinates or modified coordinate systems.

In the body of your puzzle module (i.e. after the import statements), add the following class definition:

class MyPuzzle(Pentominoes):

    height = 3
    width = 21

The first line defines a new class named "MyPuzzle" based on an existing polyform "base class" named "Pentominoes" (in the "puzzler.puzzles.polyominoes" module). You should familiarize yourself with the modules and classes in the "puzzler.puzzles" directory (also known as a Python "package"). Polyform Base classes have generic names (like "Pentominoes"), while concrete puzzle classes have specific names (like "Pentominoes5x12"). You can use either type for your base class, whichever most closely matches your puzzle.

The next lines define two class attributes, the height and width of the solution. height = 3 means that the Y coordinate may be 0, 1, or 2; because we start counting at 0, the maximum is never reached.


If this were a simple rectangular puzzle, we could now try to run the code to solve it. But there are holes in this puzzle, and we need to define them.

We do this using a "coordinates" method (indented 4 spaces):

def coordinates(self):
    holes = set(((4,1), (10,1), (16,1)))
    for y in range(self.height):
        for x in range(self.width):
            if (x,y) not in holes:
                yield puzzler.coordsys.Cartesian2D((x, y))

The first line defines the method; "self" refers to the puzzle object and is required in the definition. The second line defines "holes", a set of coordinates. Each coordinate is a tuple, a kind of list. Coordinates start at 0 (that's the way computers work), so the lower left-hand corner is (0,0).

Next we generate all possible coordinates, using "for" loops and the "range" function. Note that we can refer to attributes of the puzzle object via the "self" name ("self.height", "self.width"). The second last line checks to see if the current coordinates are in the set of holes; if they are not, we generate a coordinate.

"puzzler.coordsys.Cartesian2D" is a coordinate class. The "puzzler.coordsys" module contains classes for several coordinate systems. You should use the coordinate class appropriate for the polyform of your puzzle. Just look at the definitions of other puzzles using the same polyform to determine which coordinate class to use.

The last line uses the "yield" statement to generate one coordinate at a time to the calling code. The presence of the "yield" statement means that the "coordinates" method is actually a generator function. Since the code that calls "coordinates" merely expects a list of coordinates to be returned, the "coordinates" method could also be written as an ordinary function as follows:

def coordinates(self):
    holes = set(((4,1), (10,1), (16,1)))
    coords = []
    for y in range(self.height):
        for x in range(self.width):
            if (x,y) not in holes:
                coords.append(puzzler.coordsys.Cartesian2D((x, y)))
    return coords

The difference is that the latter variation (the function) calculates and stores all coordinates before returning any, whereas the former variation (the generator function) produces one coordinate at a time and need not store any. Either approach is perfectly acceptable in this context.

Preventing Duplicates

At this point we can run the module to solve the puzzle. The code is available as examples/ See Solve It above for instructions.

As defined, this puzzle produces 24 solutions. If you only want to see if the puzzle is solvable—if there's any solution—you're done.

But many of these solutions are duplicates, just rotated or flipped. We should take this into account, and Polyform Puzzler provides for different approaches to prevent or suppress duplicate solutions. The "check for duplicates" approach is simpler but less efficient at run time; the other approaches may run faster but take more thought. Different approaches lend themselves to different puzzles; it's up to you to choose the most suitable approach.

If a puzzle takes only a short time to run, there's no need to expend the time and effort to choose the most run-time efficient approach (the run-time gain is not worth the thinking and programming time). However, many puzzles can take significant amounts of time to run (hours, days, weeks, or longer); for these puzzles, careful programming pays dividends.

Check for Duplicates

This approach is typically the slowest to run, but is the easiest and fastest to code. It is slow because it only suppresses duplicate solutions, all of which are still calculated, rather than preventing duplicates in the first place (which is what the other approaches do).

The "check for duplicates" approach can also eat up memory for puzzles with many solutions. A copy is kept in memory for each solution in every equivalent orientation (flipped, rotated, etc.). Therefore this approach is not recommended for puzzles with many solutions (the definition of "many" depends on your system's resources and your willingness to do the extra work required by the other approaches; it could be millions of solutions or it could be thousands).

To check for duplicates, add this code to the beginning of the MyPuzzle class (above the "coordinates" method):

check_for_duplicates = True

duplicate_conditions = ({'x_reversed': True},
                        {'y_reversed': True},
                        {'x_reversed': True, 'y_reversed': True})

"check_for_duplicates" is a flag that tells Polyform Puzzler to check if a duplicate solution has already been stored. If the solution is original, Polyform Puzzler will store the formatted solution along with all variations for future duplicate checking. Each polyform and type of puzzle can have different symmetry properties, each producing a different variation; "duplicate_conditions" lists these conditions. Each item in the list is a dictionary containing a combination of symmetry properties. The entire list (along with the implied, no-change entry) should cover all possible duplicates.

(The conditions dictionary is actually passed as default-value keyword arguments to the puzzle's "format_solution" method. See that method's code or use "help(puzzle.format_solution)" in Python's interactive interpreter for details.)

Add the lines above to your puzzle module (if you have any other duplicate suppression code, remove it now), or use examples/ Running the puzzle again results in only 6 solutions, all unique.

Customize Piece Aspects

This approach can be significantly faster than checking for duplicates, since it reduces the scope of a puzzle, preventing rather than suppressing duplicates.

When a puzzle is being solved, all puzzle pieces are rotated and flipped into every possible aspect. So another way to prevent duplicates is to put limits on certain puzzle pieces to ensure that no duplicates will be possible. In other words, we can reason that if the aspects of a certain piece are restricted, we can prevent duplicates in the first place. In this puzzle, we'll restrict the "V" piece to a single aspect (no rotations or flips allowed). The "customize_piece_data" method is where we specify such restrictions:

def customize_piece_data(self):
    self.piece_data['V'][-1]['flips'] = None
    self.piece_data['V'][-1]['rotations'] = None

(This code is actually modifying a dictionary of aspect restrictions. The restrictions dictionary is passed as keyword arguments to the puzzle's "make_aspects" method. Individual restrictions vary between polyform types. See the code of the "make_aspects" method for details.)

Remove any other duplicate suppression code and add the lines above to your puzzle module (or use examples/ Running the puzzle again results in only 6 solutions, all unique. The set of solutions may differ slightly (by rotation or reflection) from the solutions produced using other duplicate-prevention techniques, but they will be equivalent.

Restrict Piece Placement

This is usually the fastest approach, reducing the scope of a puzzle, preventing rather than suppressing duplicates.

Sometimes we can take advantage of the shape and symmetries of a puzzle to further restrict the pieces. Examining the puzzle, we can conclude that a certain piece is only possible in certain positions. For example, in the example puzzle, the "X" pentomino can only be positioned one square in from either end; no other position is possible. Although this in itself does not prevent all duplicates (there is still vertical symmetry), more examination could result in other observations that, together, do prevent any duplicate solutions. For example, the "I" piece can only appear in the top or bottom rows; limiting it to the bottom row removes the vertical symmetry from the puzzle.

The following code will fix the position of the "X" and "I" pentominoes:

def build_matrix(self):
    keys = sorted(self.pieces.keys())
    x_coords, x_aspect = self.pieces['X'][0]
    translated = x_aspect.translate((1, 0))
    self.build_matrix_row('X', translated)
    i_coords, i_aspect = self.pieces['I'][1]
    for x in range(3, 17):
        translated = i_aspect.translate((x, 0))
        self.build_matrix_row('I', translated)

Let's look at this one line at a time. First, we begin the method definition:

def build_matrix(self):

Next we get a sorted list of all puzzle piece names (the keys of the "self.pieces" dictionary):

keys = sorted(self.pieces.keys())

Extract the first set of coordinates and its aspect object for the "X" piece:

x_coords, x_aspect = self.pieces['X'][0]

Other pieces may have many aspects, but "X" has full symmetry and therefore only one aspect.

Next we offset the "X" piece one square to the right:

translated = x_aspect.translate((1, 0))

Add the translated piece to the solution matrix:

self.build_matrix_row('X', translated)

We're done with the "X" piece, so remove it from the list of pieces:


Extract the second set of coordinates and its aspect object for the "I" piece:

i_coords, i_aspect = self.pieces['I'][1]

The "I" pentomino has two aspects: horizontal and vertical. The first aspect will be vertical because its coordinates sort first, so we take the second, horizontal aspect. We could also ensure that only one aspect exists using the technique from Customize Piece Aspects.

Since the "X" piece is fixed, the "I" piece cannot overlap it, so we'll start just to the right of "X", and end at the right end of the puzzle:

for x in range(3, 17):

Offset the "I" piece x squares to the right:

translated = i_aspect.translate((x, 0))

And add the translated piece to the solution matrix:

self.build_matrix_row('I', translated)

We're done with the "I" piece too:


Build the rest of the solution matrix normally:


Add the lines above to your puzzle module and remove any other duplicate suppression code. The module is available as examples/ Running the puzzle again results in only 6 solutions, all unique.

Multiple Sub-Puzzles

Depending on the puzzle and how it is subdivided, this approach can reduce the efficiency of a puzzle. This approach should only be used if none of the other approaches prove suitable.

Some puzzles can be thought of as multiple sub-puzzles. Let's use the 4×15 pentomino puzzle as an example:


Having only one aspect, the "X" pentomino is a key piece. We can prevent duplicates by limiting the possible placement of "X". We observe that "X" must either touch the bottom or the top of the puzzle. Let's limit it to touching the bottom. We can also limit "X" to the left side of the puzzle. However, there is a special case where there is still some symmetry, when "X" is centered horizontally. So we split the puzzle into two sub-puzzles.

Here is the code from the "puzzler.puzzles" module. First we have the main puzzle class, which defines a "components" class method to return a list of sub-puzzle classes:

class Pentominoes4x15(Pentominoes):

    """368 solutions"""

    height = 4
    width = 15

    def components(cls):
        return (Pentominoes4x15A, Pentominoes4x15B)

The first sub-puzzle class restricts the "X" pentomino to the lower left of the rectangle, using the Restrict Piece Placement approach. This sub-puzzle has no symmetry issues:

class Pentominoes4x15A(Pentominoes4x15):

    def build_matrix(self):
        keys = sorted(self.pieces.keys())
        x_coords, x_aspect = self.pieces['X'][0]
        for x in range(1, 6):
            translated = x_aspect.translate((x, 0))
            self.build_matrix_row('X', translated)

The second sub-puzzle places "X" in the center, touching the bottom, using the Restrict Piece Placement approach. But there is still horizontal symmetry to handle. So we use the Customize Piece Aspects approach to restrict the aspects of an asymmetrical piece, the "P" pentomino in this example; we prevent it from flipping. That takes care of the horizontal symmetry:

class Pentominoes4x15B(Pentominoes4x15):

    """symmetry: X at center; remove flip of P"""

    def customize_piece_data(self):
        self.piece_data['P'][-1]['flips'] = None

    def build_matrix(self):
        keys = sorted(self.pieces.keys())
        x_coords, x_aspect = self.pieces['X'][0]
        translated = x_aspect.translate((6, 0))
        self.build_matrix_row('X', translated)

Modify an Existing Polyform

Customize Piece Aspects


Define a New Polyform Using an Existing Coordinate System



Define a New Coordinate System