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 for duplicates, store the formatted solution for future checking, and produce and store variations of the formatted solution as well. Each polyform and type of puzzle can have different symmetry properties; "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 specific 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 Data

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. The "customize_piece_data" method is designed for this:

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. Individual restrictions vary between polyform types. The restrictions dictionary is passed as keyword arguments to the puzzles "make_aspects" method. See that method's code for specific 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.

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

Restrict Piece Placement

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

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 Data.

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_3.py. Running the puzzle again results in only 6 solutions, all unique.

This approach also reduces the scope of a puzzle, preventing rather than suppressing duplicates.

Multiple Sub-Puzzles

Some puzzles can be thought of as multiple sub-puzzles. Let's use the 4x15 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 Data 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)

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.