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/my_puzzle_2.py. 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/my_puzzle_3.py). 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)
    keys.remove('X')
    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)
    keys.remove('I')
    self.build_regular_matrix(keys)

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:

keys.remove('X')

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:

keys.remove('I')

Build the rest of the solution matrix normally:

self.build_regular_matrix(keys)

Add the lines above to your puzzle module and remove any other duplicate suppression code. The module is available as examples/my_puzzle_4.py. 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

    @classmethod
    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)
        keys.remove('X')
        self.build_regular_matrix(keys)

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)
        keys.remove('X')
        self.build_regular_matrix(keys)