puzzle.py

from collections import deque
from sys import intern


def solve(pos, depthFirst=False):
    queue = deque([pos])
    trail = {intern(pos.canonical()): None}
    solution = deque()
    load = queue.append if depthFirst else queue.appendleft

    while not pos.isgoal():
        for m in pos:
            c = m.canonical()
            if c in trail:
                continue
            trail[intern(c)] = pos
            load(m)
        pos = queue.pop()

    while pos:
        solution.appendleft(pos)
        pos = trail[pos.canonical()]

    return list(solution)


class Puzzle:
    def __init__(self, pos=None):
        if pos:
            self.pos = pos

    def __repr__(self):
        return repr(self.pos)

    def canonical(self):
        return repr(self.pos)

    def isgoal(self):
        return self.pos == self.goal

    def solve(self, depthFirst=False):
        return solve(self, depthFirst)