Depth First Backtracking Puzzle Solver

Question

There is this type of puzzle

Turtel puzzle cards

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
 """
 result = False
 if self.__color == other.__color:
 if (self.__ht == HeadTail.head and other.__ht == HeadTail.tail) or \
 (self.__ht == HeadTail.tail and other.__ht == HeadTail.head):
 result = True
 return result
 def __str__(self) -> str:
 return "{0.ht!s} {0.color!s}".format(self)
 def __eq__(self, other: 'SymbolHalf') -> bool:
 """
 two symbol halfs are equal when the attributes agree.
 :param other: the other symbol half to compare against
 """
 return self.__ht == other.__ht and self.__color == other.__color
 def __repr__(self) -> str:
 return "SymbolHalf({0.ht!r}, {0.color!r})".format(self)
class Card(object):
 """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)
class NoEmptyFieldFound(Exception):
 pass
class CardAssignment(object):
 """Assignment of cards on the NxN field."""
 def __init__(self, n: int=3) -> None:
 """
 :param int n: edge length of the square field
 """
 self.fields = [[[None, 0] for i in range(n)] for j in range(n)]
 def __str__(self) -> str:
 temp = '| '
 for row in self.fields:
 for field in row:
 temp += '{} {} '.format(field[0], field[1] // 90) # number of the card and number of left turns
 temp += '| '
 return temp
 def __getcoordinates(self, fieldnr: int):
 """
 convert the field number in the row and column index
 :param int fieldnr: the number of the field 0..n**2-1
 """
 rowlength = len(self.fields)
 assert fieldnr <= rowlength ** 2, 'Field number too high'
 rowindex = fieldnr // rowlength
 columnindex = fieldnr % rowlength
 return rowindex, columnindex
 def __getalpha(self, fieldnr: int) -> int:
 rowindex, columnindex = self.__getcoordinates(fieldnr)
 return self.fields[rowindex][columnindex][1]
 def __getcard(self, fieldnr: int) -> Card:
 rowindex, columninxex = self.__getcoordinates(fieldnr)
 return self.fields[rowindex][columninxex][0]
 def place(self, card: Card, alpha: int, fieldnr: int) -> None:
 """
 place the 'card' on field with the given number.
 :param Card card: the card to be placed
 :param int fieldnr: the number of the field
 """
 rowindex, columnindex = self.__getcoordinates(fieldnr)
 self.fields[rowindex][columnindex][0] = card
 self.fields[rowindex][columnindex][1] = alpha
 def clear(self, fieldnr: int):
 """
 remove the card from the field
 :param int fieldnr: number of the field
 """
 rowindex, columnindex = self.__getcoordinates(fieldnr)
 self.fields[rowindex][columnindex][0] = None
 self.fields[rowindex][columnindex][1] = 0
 def isoccupied(self, fieldnr: int) -> bool:
 """
 checks wether the given field is occupied by a card.
 :param int fieldnr: number of the field
 """
 rowindex, columnindex = self.__getcoordinates(fieldnr)
 return not (self.fields[rowindex][columnindex][0] is None)
 def isfull(self) -> bool:
 """
 checks if there is an empty field left
 :return: true if all fields are occupied, false otherwise
 """
 emptyfieldfound = False
 for row in self.fields:
 for field in row:
 if field[0] is None:
 emptyfieldfound = True
 return not emptyfieldfound
 def findnextfreefield(self) -> int:
 """
 finds the next free field in row major order
 :return: the number of the field
 """
 for nr in range(len(self.fields) ** 2):
 if not self.isoccupied(nr):
 return nr
 raise NoEmptyFieldFound
 def ismatching(self, card: Card, alpha: int, fieldnr: int) -> bool:
 """
 checks if the 'card' can be placed on the field with number 'fieldnr'
 as we proceed in row major order across the field we only have to check,
 if the smybols across the western and northern edge match.
 """
 rowlength = len(self.fields)
 assert fieldnr <= rowlength ** 2, 'Field number too high'
 assert isinstance(card, Card), 'object of class Card expected'
 def issamerow(fieldnr1: int, fieldnr2: int) -> bool:
 return (fieldnr1 // rowlength) == (fieldnr2 // rowlength)
 cardmatchesnorth = cardmatcheswest = True
 northernneighbour = fieldnr - rowlength # the adjacent field in northern direction has a field number -n
 if northernneighbour >= 0: # check for the border
 if self.isoccupied(northernneighbour):
 other = self.__getcard(northernneighbour)
 cardmatchesnorth = card.north(alpha).ismatching(other.south(self.__getalpha(northernneighbour)))
 westernneighbour = fieldnr - 1 # the adjacent field in western dierection has a field number -1
 if westernneighbour >= 0 and issamerow(fieldnr, westernneighbour): # check border
 if self.isoccupied(westernneighbour):
 other = self.__getcard(westernneighbour)
 cardmatcheswest = card.west(alpha).ismatching(other.east(self.__getalpha(westernneighbour)))
 return cardmatchesnorth and cardmatcheswest
class DepthFirstBacktrackingSolver(object):
 """
 Solve puzzels per depth-first backtracking
 """
 def __init__(self) -> None:
 self.solutions = []
 def __str__(self) -> str:
 temp = ''
 for s in self.solutions:
 temp += str(s)
 return temp
 def findsolutions(self, assignment: CardAssignment, unusedcards: list) -> list:
 """
 take a partial assignment and try to add one more card from the list of free cards to it
 recursively walk the game tree depth first until a complete solution is found
 :param CardAssignment assignment: current assignment of cards on the field
 :param list unusedcards: list of unused cards
 :return list: list of the solutions
 """
 assert isinstance(assignment, CardAssignment), 'object of class CardAssignment expectd'
 assert isinstance(unusedcards, list), 'object of class list expected'
 solution = []
 freefieldnr = assignment.findnextfreefield()
 for card in unusedcards: # try every card
 for alpha in [0, 90, 180, 270]: # in all possible positions
 if assignment.ismatching(card, alpha, freefieldnr):
 assignment.place(card, alpha, freefieldnr)
 if assignment.isfull(): # as we only place a card when it matches, a full field is a solution
 solution.append(deepcopy(assignment))
 else:
 remainingcards = copy(unusedcards)
 remainingcards.remove(card) # remove the card we just placed from the list
 solution.extend(self.findsolutions(assignment, remainingcards))
 assignment.clear(freefieldnr) # clear the field to continue the search for the other solutions
 return solution
# north west south east
Turtelcards = [Card(1, SymbolHalf(HeadTail.tail, Color.green), SymbolHalf(HeadTail.head, Color.orange), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.brown)),
 Card(2, SymbolHalf(HeadTail.tail, Color.orange), SymbolHalf(HeadTail.head, Color.brown), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.green)),
 Card(3, SymbolHalf(HeadTail.tail, Color.brown), SymbolHalf(HeadTail.head, Color.green), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.orange)),
 Card(4, SymbolHalf(HeadTail.tail, Color.orange), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.head, Color.green), SymbolHalf(HeadTail.tail, Color.brown)),
 Card(5, SymbolHalf(HeadTail.tail, Color.green), SymbolHalf(HeadTail.head, Color.brown), SymbolHalf(HeadTail.head, Color.green), SymbolHalf(HeadTail.tail, Color.orange)),
 Card(6, SymbolHalf(HeadTail.tail, Color.blue), SymbolHalf(HeadTail.head, Color.orange), SymbolHalf(HeadTail.head, Color.green), SymbolHalf(HeadTail.tail, Color.brown)),
 Card(7, SymbolHalf(HeadTail.tail, Color.blue), SymbolHalf(HeadTail.head, Color.brown), SymbolHalf(HeadTail.head, Color.green), SymbolHalf(HeadTail.tail, Color.orange)),
 Card(8, SymbolHalf(HeadTail.tail, Color.green), SymbolHalf(HeadTail.head, Color.orange), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.brown)),
 Card(9, SymbolHalf(HeadTail.tail, Color.blue), SymbolHalf(HeadTail.head, Color.orange), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.brown))
]
def main():
 solver = DepthFirstBacktrackingSolver()
 emptyassignment = CardAssignment()
 solutions = solver.findsolutions(emptyassignment, Turtelcards)
 for solution in solutions:
 print(solution)
if __name__ == '__main__':
 main()

Answer 1

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 arguments")
 self.id = id
 self.sides = sides
 def orientations(self):
 sides_rot = deque(self.sides)
 for i in range(4):
 yield OrientedCard(self.id, i, *sides_rot)
 sides_rot.rotate(1)

The orientation is stored here for printing.

SymbolHalf similarly seems like it could be reduced to a namedtuple:

class SymbolHalf(namedtuple("SymbolHalfFields", ["body_half", "color"])):
 __slots__ = ()
 def matches(self, other: 'SymbolHalf') -> bool:
 """
 :param SymbolHalf other:
 :return: Whether the symbols are two halves of the same turtle
 """
 return self.color == other.color and self.body_half != other.body_half

__slots__ = () is useful when inheriting from namedtuple since having a __dict__ breaks some namedtuple methods.

Back to find_solutions, we have

if assignment.is_matching(oriented_card, field_num):

is_matching seems like the wrong question here; it's more like could_accept. In it, you have

def could_accept(self, card: OrientedCard, field_num: int) -> bool:
 """
 checks if the 'card' can be placed on the field with number 'field_num'
 as we proceed in row major order across the field we only have to check,
 if the smybols across the western and northern edge match.
 """
 rowlength = len(self.fields)
 assert field_num <= rowlength ** 2, 'Field number too high'
 assert isinstance(card, OrientedCard), 'object of class OrientedCard expected'
 def issamerow(fieldnr1: int, fieldnr2: int) -> bool:
 return (fieldnr1 // rowlength) == (fieldnr2 // rowlength)
 card_matches_north = card_matches_west = True
 # the adjacent field in northern direction has a field number -n
 northern_neighbour = field_num - rowlength 
 # check for the border
 if northern_neighbour >= 0:
 if self.is_occupied(northern_neighbour):
 other = self._get_card(northern_neighbour)
 card_matches_north = card.north.matches(other.south)
 # the adjacent field in western dierection has a field number -1
 western_neighbour = field_num - 1
 # check border
 if western_neighbour >= 0 and issamerow(field_num, western_neighbour):
 if self.is_occupied(western_neighbour):
 other = self._get_card(western_neighbour)
 card_matches_west = card.west.matches(other.east)
 return card_matches_north and card_matches_west

I don't like the idea that you're decoding and re-encoding the position into a single number. I also don't like the assumption that the board is square; it seems like a rather pointless and unhelpful one. Those is_occupied checks are probably wrong, too.

So lets try to fix that up and make this class a bit comfier. First, cache the width and height

def __init__(self, width: int=3, height: int=3) -> None:
 self.width = width
 self.height = height
 self.fields = [[None] * height for _ in range(width)]

Make a cannonical way to decode:

def position_of_num(field_num: int):
 if field_num > self.width * self.height:
 raise ValueError("Field value too large")
 return field_num // self.width, field_num % self.width

(this is your _get_coordinates but simpler and for public use).

We make a simpler is_full:

def is_full(self) -> bool:
 """
 :return: whether there is no unfilled field in the grid
 """
 return not any(None in col for col in self.fields)

Then make could_accept take an x and y instead:

def could_accept(self, card: OrientedCard, x: int, y: int) -> bool:
 """
 Return whether the card can be placed at the given position.
 """
 if not (0 <= x < self.width and 0 <= y < self.height):
 raise IndexError("Index out of bounds")
 assert isinstance(card, OrientedCard), 'object of class OrientedCard expected'
 if x and not card.north.matches(self.fields[x - 1][y].south):
 return False
 if y and not card.west.matches(self.fields[x][y - 1].east):
 return False
 return True

That's all you really need from this.

could_accept is fundementally wrong, though, since could_accept assumes a given iteration order. But classes should be distinct from the algorithms that use them, so it makes sense to me for this to be a local function of some kind. I'd also remove the index check since it'd be thrown for you once you actually try to index, but YMMV.

The is_full checks are redundant since you know that it's full only when you've used all the unused cards.

You do

unused_cards = copy(unused_cards)
# remove the card we just placed from the list
unused_cards.remove(card)
yield from find_solutions(assignment, unused_cards, field_num+1)

traditionally one does

unused_cards.remove(card)
yield from find_solutions(assignment, unused_cards, field_num+1)
unused_cards.add(card)

because this is much faster. However, this doesn't work if you're iterating over the values at the same time. The simplest nicer solution I see would be to use a set and do

# If len(unused_cards) > 1, we've got more cards to place
if len(unused_cards) > 1:
 yield from find_solutions(assignment, unused_cards - {card}, field_num+1)
else:
 yield deepcopy(assignment)

It is possible to avoid this by doing more intelligent work (such as maksing values), but since we search the whole tree this doesn't actually help much.

TurtelCards currently looks like

Turtelcards = {Card(1, SymbolHalf(HeadTail.tail, Color.green), SymbolHalf(HeadTail.head, Color.orange), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.brown)),
 Card(2, SymbolHalf(HeadTail.tail, Color.orange), SymbolHalf(HeadTail.head, Color.brown), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.green)),
 Card(3, SymbolHalf(HeadTail.tail, Color.brown), SymbolHalf(HeadTail.head, Color.green), SymbolHalf(HeadTail.head, Color.blue), SymbolHalf(HeadTail.tail, Color.orange)),
 # ...
}

I think it's much easier to read as

def make_symbol_half(string):
 part, color = string.split()
 return SymbolHalf(HeadTail.__members__[part], Color.__members__[color])
def make_card(card_id, *symbols):
 return Card(card_id, *map(make_symbol_half, symbols))
Turtelcards = {
 make_card(1, 'tail green', 'head orange', 'head blue', 'tail brown'),
 make_card(2, 'tail orange', 'head brown', 'head blue', 'tail green'),
 make_card(3, 'tail brown', 'head green', 'head blue', 'tail orange'),
 make_card(4, 'tail orange', 'head blue', 'head green', 'tail brown'),
 make_card(5, 'tail green', 'head brown', 'head green', 'tail orange'),
 make_card(6, 'tail blue', 'head orange', 'head green', 'tail brown'),
 make_card(7, 'tail blue', 'head brown', 'head green', 'tail orange'),
 make_card(8, 'tail green', 'head orange', 'head blue', 'tail brown'),
 make_card(9, 'tail blue', 'head orange', 'head blue', 'tail brown')
}

There's no harm in doing a bit of parsing at the start since it's only run once. These probably shouldn't be module-scoped, though, so I'd put them in main.

Now, half of the time seems to be spent iterating over orientations, so you should cache these.

class Card:
 def __init__(self, num: int, *sides):
 if len(sides) != 4:
 raise ValueError("Cards have exactly 4 sides, expected 4 arguments")
 self.num = num
 self.sides = sides
 self.orientations = tuple(self._make_orientations())
 def _make_orientations(self):
 sides_rot = deque(self.sides)
 for i in range(4):
 yield OrientedCard(self.num, i, *sides_rot)
 sides_rot.rotate(1)

Looking at CardAssignment's __str__, we have

def __str__(self) -> str:
 temp = '| '
 for col in self.fields:
 for field in col:
 # number of the card and number of left turns
 temp += '{} {} '.format(field.num, field.rotation) 
 temp += '| '
 return temp

This uses += in a loop, which is \$\mathcal{O}(n^2)\$ and disadvised of. This would better be

def __str__(self) -> str:
 def format_col(col):
 return " ".join("{} {}".format(field.num, field.rotation) for field in col)
 return "| {} |".format(" | ".join(map(format_col, self.fields)))

That about finishes it. There are much faster ways to solve this, but they'd all involve larger core changes.

Here's the updated code:

from collections import deque, namedtuple
from copy import deepcopy
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(namedtuple("SymbolHalfFields", ["body_half", "color"])):
 __slots__ = ()
 def matches(self, other: 'SymbolHalf') -> bool:
 """
 :param SymbolHalf other:
 :return: Whether the symbols are two halves of the same turtle
 """
 return self.color == other.color and self.body_half != other.body_half
OrientedCard = namedtuple("OrientedCard", ["num", "rotation", "north", "east", "south", "west"])
class Card:
 def __init__(self, num: int, *sides):
 if len(sides) != 4:
 raise ValueError("Cards have exactly 4 sides, expected 4 arguments")
 self.num = num
 self.sides = sides
 self.orientations = tuple(self._make_orientations())
 def _make_orientations(self):
 sides_rot = deque(self.sides)
 for i in range(4):
 yield OrientedCard(self.num, i, *sides_rot)
 sides_rot.rotate(1)
class CardAssignment:
 """Assignment of cards on the NxM field."""
 def __init__(self, width: int=3, height: int=3) -> None:
 self.width = width
 self.height = height
 self.fields = [[None] * height for _ in range(width)]
 def __str__(self) -> str:
 def format_col(col):
 return " ".join("{} {}".format(field.num, field.rotation) for field in col)
 return "| {} |".format(" | ".join(map(format_col, self.fields)))
 def position_of_num(self, field_num: int):
 """Decode field number into an (x, y) tuple."""
 if field_num > self.width * self.height:
 raise ValueError("Field value too large")
 return field_num // self.width, field_num % self.width
def northwest_could_accept(assignment, card: OrientedCard, x: int, y: int) -> bool:
 """
 Return whether the card can be placed at the given position.
 This only checks against northward and westward tiles.
 """
 assert isinstance(card, OrientedCard), 'object of class OrientedCard expected'
 if x and not card.north.matches(assignment.fields[x - 1][y].south):
 return False
 if y and not card.west.matches(assignment.fields[x][y - 1].east):
 return False
 return True
def find_solutions(assignment: CardAssignment, unused_cards: set, field_num: int=0):
 """
 Take a partial assignment and find complete assignments from the unused_cards.
 Yield each solution.
 :param CardAssignment assignment: current assignment of cards on the field
 :param set unused_cards: set of cards to fill the unfilled slots with
 :param int field_num: index of first field number with an empty slot, or earlier
 :return generator: iterator of solutions
 """
 assert isinstance(assignment, CardAssignment), 'object of class CardAssignment expected'
 assert isinstance(unused_cards, set), 'object of class list expected'
 x, y = assignment.position_of_num(field_num)
 # try every card in all possibly positions
 for card in unused_cards:
 for oriented_card in card.orientations:
 if northwest_could_accept(assignment, oriented_card, x, y):
 assignment.fields[x][y] = oriented_card
 # If len(unused_cards) > 1, we've got more cards to place
 if len(unused_cards) > 1:
 yield from find_solutions(assignment, unused_cards - {card}, field_num+1)
 else:
 yield deepcopy(assignment)
 # clear the field to continue the search for the other solutions
 assignment.fields[x][y] = None
def main():
 def make_symbol_half(string):
 part, color = string.split()
 return SymbolHalf(HeadTail.__members__[part], Color.__members__[color])
 def make_card(card_id, *symbols):
 return Card(card_id, *map(make_symbol_half, symbols))
 Turtelcards = {
 make_card(1, 'tail green', 'head orange', 'head blue', 'tail brown'),
 make_card(2, 'tail orange', 'head brown', 'head blue', 'tail green'),
 make_card(3, 'tail brown', 'head green', 'head blue', 'tail orange'),
 make_card(4, 'tail orange', 'head blue', 'head green', 'tail brown'),
 make_card(5, 'tail green', 'head brown', 'head green', 'tail orange'),
 make_card(6, 'tail blue', 'head orange', 'head green', 'tail brown'),
 make_card(7, 'tail blue', 'head brown', 'head green', 'tail orange'),
 make_card(8, 'tail green', 'head orange', 'head blue', 'tail brown'),
 make_card(9, 'tail blue', 'head orange', 'head blue', 'tail brown')
 }
 for solution in find_solutions(CardAssignment(), Turtelcards):
 print(solution)
if __name__ == '__main__':
 main()

• uli: This is much appreciated!