Depth First Backtracking Puzzle Solver

There is this type of puzzle

that can easily be solved with a depth-first backtracking solver. I wrote one in python 3.4 and like to get some feedback.

I'm especially interested in the following points:

• deepcopy. The usage of deepcopy in DepthFirstBacktrackingSolver.findsolutions is somewhat ugly. As Python simply binds objects to identifies I need to request a copy a of solution, otherwise the solution would be overwritten when the next solution is constructed. Is the deepcopy really necessary?

-
copy. The usage of copy in DepthFirstBacktrackingSolver.findsolutions is ugly too. I could avoid the copy by temporarily removing the card from the list of available cards for the rest of this search tree branch:

unusedcards.remove(card)  # remove the card we just placed from the list
solution.extend(self.findsolutions(assignment, unusedcards))
unusedcards.append(card)  # reappend the card to explore other solutions

-
Exploiting symmetry. Every solution can be rotated and three more solutions are obtained. I haven’t found a good way to exploit the symmetry in this type of game. Especially with larger boards 5x5, 6x6, 7x7, 8x8, ... the possible savings in pruning the
search tree should be worth incorporating this.

• And all else that you can spot.

```
from copy import deepcopy
from copy import copy
from enum import Enum

class HeadTail(Enum):
head = 1
tail = 2

class Color(Enum):
brown = 1
orange = 2
green = 3
blue = 4
red = 5
grey = 6
yellow = 7

class SymbolHalf(object):
"""One half of a symbol."""

def __init__(self, ht, color) -> None:
self.__ht = ht
self.__color = color

@property
def ht(self):
return self.__ht

@property
def farbe(self):
return self.__color

def ismatching(self, other: 'SymbolHalf') -> bool:
"""
:param other: another symbol half
:return: true when both symbol halfs match, false otherwise

Now, I'm really not a fan of comments on the end of lines, so I'd fix that all up. You're also using everythingisonewordcase instead of snake_case; the convention is strongly towards the latter.

Since this is Python 3, you don't need to inherit from object, but... DepthFirstBacktrackingSolver is just a function, albeit one that pretends to be more. Well, don't let it! All it's done is give you unused state and a broken unused __str__ method.

def find_solutions(assignment: CardAssignment, unused_cards: list) -> list:
    # Same as before

Then I suggest making it yield its solutions:

def find_solutions(assignment: CardAssignment, unused_cards: list) -> list:
    """..."""
    assert isinstance(assignment, CardAssignment), 'object of class CardAssignment expected'
    assert isinstance(unused_cards, list), 'object of class list expected'

    free_field_nr = assignment.find_next_free_field()
    # try every card
    for card in unused_cards:
        # in all possible positions
        for alpha in [0, 90, 180, 270]:
            if assignment.is_matching(card, alpha, free_field_nr):
                assignment.place(card, alpha, free_field_nr)
                # as we only place a card when it matches, a full field is a solution
                if assignment.is_full():
                    yield deepcopy(assignment)
                else:
                    remaining_cards = copy(unused_cards)
                    # remove the card we just placed from the list
                    remaining_cards.remove(card)
                    yield from find_solutions(assignment, remaining_cards)
                # clear the field to continue the search for the other solutions
                assignment.clear(free_field_nr)

Now, your docstring is covered in implementation details. It should instead read more like

Take a partial assignment and find complete assignments from the unused_cards list.
Yield each solution.

:param CardAssignment assignment: current assignment of cards on the field
:param list unused_cards: unused cards
:return generator: iterator of solutions

Going through the logic, we have

free_field_nr = assignment.find_next_free_field()

This seems a little unneeded - you can just increment this value each time you recurse.

You then do

for card in unused_cards:
    for alpha in [0, 90, 180, 270]:

This seems suboptimal:

• You're iterating over a list instead of a tuple

• The possibilities (0, 90, etc.) are sparse

• The type is far too large; almost all numbers are invalid rotations

Much simpler would be

for card in unused_cards:
    for oriented_card in card.orientations():

This removes the fiddling with rotations altogether. Further, it means that the functions you pass it to only need to take an oriented card, which can be a different type. So let's look at the card type.

class Card:
    """A card of a puzzle carries four symbol halfs."""

    def __init__(self, nr: int, n: SymbolHalf, w: SymbolHalf, s: SymbolHalf, o: SymbolHalf) -> None:
        """
        :param int nr: number of the card
        :param SymbolHalf n: northern symbol half
        :param SymbolHalf s: southern symbol half
        :param SymbolHalf w: western symbol half
        :param SymbolHalf o: eastern symbol half
        """
        assert isinstance(nr, int)
        self.nr = nr
        self.__symbole = [n, o, s, w]

    def __str__(self) -> str:
        return str(self.nr)

    def __getsymbolhalf(self, position: int, alpha: int) -> SymbolHalf:
        """
        get the symbol half in 'position' of the card accounting for the rotation 'alpha' of the card.
        :param int position: cardinal direction
        :param int alpha: rotation angle of the card 0 90 180 270
        :return: the requested symbol half
        """
        return self.__symbole[(alpha // 90 + position) % 4]

    def north(self, alpha: int) -> SymbolHalf:
        return self.__getsymbolhalf(0, alpha)

    def east(self, alpha: int) -> SymbolHalf:
        return self.__getsymbolhalf(1, alpha)

    def south(self, alpha: int) -> SymbolHalf:
        return self.__getsymbolhalf(2, alpha)

    def west(self, alpha: int) -> SymbolHalf:
        return self.__getsymbolhalf(3, alpha)

Don't use __mangled names; just use _private names unless you really need name mangling (which you should try and avoid).

Your __str__ is also misleading. If you wish to do something like this, just print .nr directly. Otherwise a Card looks like a number, which is a pain for debugging.

Your _getsymbolhalf does a lot of work we're going to try and avoid, so lets work out a better way of doing this.

```
from collections import deque, namedtuple

OrientedCard = namedtuple("OrientedCard", ["id", "orientation", "north", "east", "south", "west"])

class Card:
def __init__(self, id: int, *sides):
if len(sides) != 4:
raise ValueError("Cards have exactly 4 sides, expected 4 argumen

StackExchange Code Review Q#83607, answer score: 3