I wrote a simple 8-Puzzle and solver and am interested in seeing how it might be improved. Please let me know if any style or design changes might enhance the readability/performance of my code.import randomimport itertoolsimport collectionsclass Node:        A class representing an Solver node    - 'puzzle' is a Puzzle instance    - 'parent' is the preceding node generated by the solver, if any    - 'action' is the action taken to produce puzzle, if any        def __init__(self, puzzle, parent=None, action=None):        self.puzzle = puzzle        self.parent = parent        self.action = action    @property    def state(self):                Return a hashable representation of self                return str(self)    @property     def path(self):                Reconstruct a path from to the root 'parent'                node, p = self, []        while node:            p.append(node)            node = node.parent        yield from reversed(p)    @property    def solved(self):         Wrapper to check if 'puzzle' is solved         return self.puzzle.solved    @property    def actions(self):         Wrapper for 'actions' accessible at current state         return self.puzzle.actions    def __str__(self):        return str(self.puzzle)class Solver:        An '8-puzzle' solver    - 'start' is a Puzzle instance        def __init__(self, start):        self.start = start    def solve(self):                Perform breadth first search and return a path        to the solution, if it exists                 queue = collections.deque([Node(self.start)])        seen  = set()        seen.add(queue[0].state)        while queue:            node = queue.pop()            if node.solved:                return node.path            for move, action in node.actions:                child = Node(move(), node, action)                if child.state not in seen:                    queue.appendleft(child)                    seen.add(child.state)class Puzzle:        A class representing an '8-puzzle'.    - 'board' should be a square list of lists with integer entries 0...width^2 - 1       e.g. [[1,2,3],[4,0,6],[7,5,8]]        def __init__(self, board):        self.width = len(board[0])        self.board = board    @property    def solved(self):                The puzzle is solved if the flattened board's numbers are in        increasing order from left to right and the '0' tile is in the        last position on the board                N = self.width * self.width        return str(self) == ''.join(map(str, range(1,N))) + '0'    @property     def actions(self):                Return a list of 'move', 'action' pairs. 'move' can be called        to return a new puzzle that results in sliding the '0' tile in        the direction of 'action'.                def create_move(at, to):            return lambda: self._move(at, to)        moves = []        for i, j in itertools.product(range(self.width),                                      range(self.width)):            direcs = {'R':(i, j-1),                      'L':(i, j+1),                      'D':(i-1, j),                      'U':(i+1, j)}            for action, (r, c) in direcs.items():                if r >= 0 and c >= 0 and r < self.width and c < self.width and \                   self.board[r][c] == 0:                    move = create_move((i,j), (r,c)), action                    moves.append(move)        return moves    def shuffle(self):                Return a new puzzle that has been shuffled with 1000 random moves                puzzle = self        for _ in range(1000):            puzzle = random.choice(puzzle.actions)[0]()        return puzzle    def copy(self):                Return a new puzzle with the same board as 'self'                board = []        for row in self.board:            board.append([x for x in row])        return Puzzle(board)    def _move(self, at, to):                Return a new puzzle where 'at' and 'to' tiles have been swapped.        NOTE: all moves should be 'actions' that have been executed                copy = self.copy()        i, j = at        r, c = to        copy.board[i][j], copy.board[r][c] = copy.board[r][c], copy.board[i][j]        return copy    def pprint(self):        for row in self.board:            print(row)        print()    def __str__(self):        return ''.join(map(str, self))    def __iter__(self):        for row in self.board:            yield from row# example of use     board = [[1,2,3],[4,0,6],[7,5,8]]puzzle = Puzzle(board)puzzle = puzzle.shuffle()s = Solver(puzzle)p = s.solve()for node in p:    print(node.action)    node.puzzle.pprint()
Python 8-Puzzle and solver
python;algorithm;pathfinding;breadth first search;sliding tile puzzle
Even though this is a brute-force enumeration algorithm, we can still make a few optimizations.TerminationYou check whether each puzzle is solved when you remove it from the queue.  It would be more efficient to check when enqueuing it.  The difference is that you won't realize that you've already solved the puzzle until after trying all of the other guesses for paths of the same length.  For a 33 puzzle, if it reaches 20 steps, that's an extra 40000 guesses that you would check unnecessarily.RepresentationStoring the board as a flattened array would make it more convenient to copy and to search.  (You eventually flatten every one of your puzzle states anyway when calling Puzzle.solved().)  Another advantage is that the location of any tile (or hole) can be represented as a single integer rather than as a pair of numbers  this is important, as we shall see.In Puzzle.actions(), you generate the list of all possible moves.  To do so, you must find up to four neighbours of the hole.  You accomplish that by searching all width * width locations for the hole.  If it were a linear list, we could just call .index(0) instead of doing a two-dimensional search.  Better yet, just cache the location of the hole.With a linear representation, you can uniquely identify a move as the \$\Delta \mathrm{index}\$ of the hole (1 for horizontal, and width for vertical movements).But it gets even better.  You can reconstruct the entire history of a puzzle state if you know the most recent state and the indexes of the holes of all the past states.  That, I think, is preferable to keeping a linked list of 33 snapshots of every previous attempt, as you do in your Node class.StringificationFor the algorithm to work, you need to keep a set of all previously seen board states.  Items to be placed in a set must be hashable, and to meet that requirement, you store Node.state, which returns a stringified representation of the data.  I find that unclean.  The __str__() function would be more appropriate for producing a human-friendly display, but curiously, you defined a specialized Puzzle.pprint() method for that.A more proper solution would be to make Puzzle hashable by defining its __hash__() and __eq__() methods.ClassesNode is too generic of a name.  I suggest MoveSequence.The code would be easier to understand if you presented the classes in reverse order: Puzzle, then MoveSequence, then Solver.Rather than defining Puzzle.copy() and Puzzle._move(), I would make Puzzle immutable, such that Puzzle.move() always returns a new Puzzle.Instead of hard-coding 1000 moves for Puzzle.shuffle(), it should take a moves parameter that defaults to 1000.Suggested implementationfrom collections import dequefrom itertools import chain, teefrom math import sqrtfrom random import choiceclass Puzzle:    HOLE = 0        A class representing an '8-puzzle'.    - 'board' should be a square list of lists with integer entries 0...width^2 - 1       e.g. [[1,2,3],[4,0,6],[7,5,8]]        def __init__(self, board, hole_location=None, width=None):        # Use a flattened representation of the board (if it isn't already)        self.board = list(chain.from_iterable(board)) if hasattr(board[0], '__iter__') else board        self.hole = hole_location if hole_location is not None else self.board.index(Puzzle.HOLE)        self.width = width or int(sqrt(len(self.board)))    @property    def solved(self):                The puzzle is solved if the flattened board's numbers are in        increasing order from left to right and the '0' tile is in the        last position on the board                return self.board == list(range(1, self.width * self.width)) + [Puzzle.HOLE]    @property     def possible_moves(self):                A generator for the possible moves for the hole, where the        board is linearized in row-major order.  Possibilities are        -1 (left), +1 (right), -width (up), or +width (down).                # Up, down        for dest in (self.hole - self.width, self.hole + self.width):            if 0 <= dest < len(self.board):                yield dest        # Left, right        for dest in (self.hole - 1, self.hole + 1):            if dest // self.width == self.hole // self.width:                yield dest    def move(self, destination):                Move the hole to the specified index.                board = self.board[:]        board[self.hole], board[destination] = board[destination], board[self.hole]        return Puzzle(board, destination, self.width)    def shuffle(self, moves=1000):                Return a new puzzle that has been shuffled with random moves                p = self        for _ in range(moves):            p = p.move(choice(list(p.possible_moves)))        return p    @staticmethod    def direction(a, b):                The direction of the movement of the hole (L, R, U, or D) from a to b.                if a is None:            return None        return {                     -a.width: 'U',            -1: 'L',    0: None,    +1: 'R',                     +a.width: 'D',        }[b.hole - a.hole]    def __str__(self):        return \n.join(str(self.board[start : start + self.width])                         for start in range(0, len(self.board), self.width))    def __eq__(self, other):        return self.board == other.board    def __hash__(self):        h = 0        for value, i in enumerate(self.board):            h ^= value << i        return hclass MoveSequence:        Represents the successive states of a puzzle taken to reach an end state.        def __init__(self, last, prev_holes=None):        self.last = last        self.prev_holes = prev_holes or []    def branch(self, destination):                Makes a MoveSequence with the same history followed by a move of        the hole to the specified destination index.                return MoveSequence(self.last.move(destination),                            self.prev_holes + [self.last.hole])    def __iter__(self):                Generator of puzzle states, starting with the initial configuration                states = [self.last]        for hole in reversed(self.prev_holes):            states.append(states[-1].move(hole))        yield from reversed(states)class Solver:        An '8-puzzle' solver    - 'start' is a Puzzle instance        def __init__(self, start):        self.start = start    def solve(self):                Perform breadth-first search and return a MoveSequence of the solution,        if it exists                 queue = deque([MoveSequence(self.start)])        seen  = set([self.start])        if self.start.solved:            return queue.pop()        for seq in iter(queue.pop, None):            for destination in seq.last.possible_moves:                attempt = seq.branch(destination)                if attempt.last not in seen:                    seen.add(attempt.last)                    queue.appendleft(attempt)                    if attempt.last.solved:                        return attempt# https://docs.python.org/3/library/itertools.html#itertools-recipesdef pairwise(iterable):    s -> (s0,s1), (s1,s2), (s2, s3), ...    a, b = tee(iterable)    next(b, None)    return zip(a, b)if __name__ == '__main__':    board = [[1,2,3],             [4,0,6],             [7,5,8]]    puzzle = Puzzle(board).shuffle()    print(puzzle)    move_seq = iter(Solver(puzzle).solve())    for from_state, to_state in pairwise(move_seq):        print()        print(Puzzle.direction(from_state, to_state))        print(to_state)