I plan to implement a few other solvers (depth first search, A*, etc), hence why I'm using the abstract base class (which is new to me). I'm using Python 3.6, so you'll see f-string literals. I would appreciate any positive feedback (yay!) or, even more importantly, constructive (yay!) criticism.

import abc
from argparse import ArgumentParser
from collections import deque
from math import sqrt
from resource import getrusage, RUSAGE_SELF
from time import time

import numpy as np

class Board:
    def __init__(self, tiles: str, hole: str = '0', sz: int = None):
        board_ = tiles.split(',')
        self._sz = sz or int(sqrt(len(board_)))
        self._sorted_tokens = [str(x) for x in range(self._sz ** 2)]
        self._goal = np.reshape(self._sorted_tokens, (self._sz, -1))
        self._state = np.reshape(board_, (self._sz, -1))
        self._hole = hole

    def __repr__(self):
        return str(self._state)

    def goal(self):
        return ','.join(self._sorted_tokens)

    def string(self):
        return self.stringify(self._state)

    def state(self):
        return self._state

    def stringify(state):
        return ','.join(state.flatten())

    def hole_pos(self):
        pos = np.where(self._state == self._hole)
        return pos[0][0], pos[1][0]

    def tile(self, pos):
        if pos[0] < 0 or pos[1] < 0:
            raise ValueError('Tile out of bounds!')
        return self._state[pos]

    def act(self, action):
        hole = self.hole_pos()
        lut = {
            'Up': (hole[0] - 1, hole[1]),
            'Down': (hole[0] + 1, hole[1]),
            'Left': (hole[0], hole[1] - 1),
            'Right': (hole[0], hole[1] + 1)
        pos = lut[action]
        board_ = self.swap(pos)
        return board_

    def actions(self):
        find neighboring tiles to hole position
        hole = self.hole_pos()
        actions_ = []
        if hole[0] - 1 >= 0:
        if hole[0] + 1 < self._sz:
        if hole[1] - 1 >= 0:
        if hole[1] + 1 < self._sz:
        return actions_

    def swap(self, pos):
        position is tuple (R,C) of neighboring tile to hole
            hole = self.hole_pos()
            tile = self.tile(pos)
            temp_state = self._state.copy()
            temp_state[pos[0]][pos[1]] = self._hole
            temp_state[hole[0]][hole[1]] = tile
            return Board(self.stringify(temp_state),
        except ValueError:
            return None

class Node:
    def __init__(self, state=None, action=None, path_cost=None, parent=None):
        self._state = state
        self._action = action
        self._path_cost = path_cost
        self._parent = parent

    def __repr__(self):
        return str({'state': self._state.state,
                    'action': self._action,
                    'path_cost': self._path_cost,
                    'parent': self.parent})

    def __iter__(self):
        node = self
        while node:
            yield node
            node = node._parent

    def state(self):
        return self._state

    def action(self):
        return self._action

    def path_cost(self):
        return self._path_cost

    def parent(self):
        return self._parent

    def depth(self):
        return sum(1 for _ in self) - 1  # to account for 0 indexing

class Solver(metaclass=abc.ABCMeta):
    def __init__(self, start_board: Board, depth: int = 4):
        self._goal = start_board.goal
        self._start_board = start_board
        self._frontier = deque()
        self._explored = set()
        self._path_cost = 0
        self._nodes_expanded = 0
        self._fringe_sz = 0
        self._max_fringe_sz = 0
        self._search_depth = 0
        self._max_search_depth = 0
        self._running_time = 0
        self._depth_limit = depth

    def nodes_expanded(self):
        return self._nodes_expanded

    def fringe_size(self):
        return self._fringe_sz

    def max_fringe_size(self):
        return self._max_fringe_sz

    def search_depth(self):
        return self._search_depth

    def max_search_depth(self):
        return self._max_search_depth

    def running_time(self):
        return self._running_time

    def update_fringe_size(self):
        self._fringe_sz = len(self._frontier)
        if self._fringe_sz > self._max_fringe_sz:
            self._max_fringe_sz = self._fringe_sz

    def solve(self):
        To be implemented by detailed search strategies

class DFS(Solver):
    def solve(self):

class AST(Solver):
    def solve(self):

class IDA(Solver):
    def solve(self):

class BFS(Solver):
    def solve(self):
        start_time = time()
        root = Node(state=self._start_board,
        if root.state.string == self._goal:
            self._search_depth = root.depth
            self._running_time = time() - start_time
            return root
        while True:
            if len(self._frontier) == 0:
                self._running_time = time() - start_time
                raise ValueError('Goal not found.')
            node = self._frontier.popleft()
            if node.depth > self._depth_limit:
                raise RuntimeError
            if node.state.string == self._goal:
                self._search_depth = node.depth
                self._running_time = time() - start_time
                return node
            self._nodes_expanded += 1
            actions = node.state.actions()
            for action in actions:
                state = node.state.act(action)
                child = Node(state=state,
                if child.depth > self._max_search_depth:
                    self._max_search_depth = child.depth
                if (child.state.string not in self._explored) and (child not in self._frontier):

class Summary:
    def __init__(self, child: Node):
        self._child = child

    def path_cost(self):
        return sum(n.path_cost for n in self._child)

    def actions(self):
        return list(reversed([n.action for n in self._child]))[1:]

    def search_depth(self):
        return self._child.depth

if __name__ == "__main__":
        parser = ArgumentParser()
        parser.add_argument("solver", help="algorithm (bfs | dfs)")
        parser.add_argument("board", help="board string (0,1,2,3...)")
        args = parser.parse_args()
        board = Board(tiles=args.board)
        print("***STARTING STATE***")
        algorithms = {
            'bfs': BFS(board, depth=100),
            # 'dfs': DFS(board, depth=100),
            # 'ast': BFS(board, depth=100),
            # 'ida': BFS(board, depth=100)

        search = algorithms[args.solver]
        res = search.solve()
        print("***SOLUTION STATE***")
        print(f"nodes expanded {search.nodes_expanded}")
        summary = Summary(res)
        print(f"path cost {summary.path_cost()}")
        print(f"actions {summary.actions()}")
        print(f"fringe size: {search.fringe_size}")
        print(f"max_fringe_size: {search.max_fringe_size}")
        print(f"search depth {search.search_depth}")
        print(f"max search depth {search.max_search_depth}")
        print(f"running time {search.running_time}")
        print(f"memory usage {getrusage(RUSAGE_SELF)[2]}")
    except TypeError as e:
  • \$\begingroup\$ @mayo Please write all critiques in answers, not comments. Comments are for seeking clarification to the question and are subject to deletion. \$\endgroup\$ – 200_success Feb 22 '17 at 23:38

Here is a high-level overview without diving into the implementation details:

  • the solve() of your BFS class is not readable and quite lengthy - split it into multiple methods and/or add meaningful comments
  • overall the program is long - see if you can split it into multiple importable modules
  • I would also extract the "reading command-line arguments" and "reporting the results" code blocks into separate functions
  • the last set of print() calls can be replaced with a single print() call and a multi-line string
  • the Solver class may be rewritten using the attrs package making the code more readable avoiding the boilerplate parts
  • according to the Docstring Convention, you should start your docstring with a capital letter and have a dot at the end of sentences. And, if a docstring fits a single line, define it on a single line.
  • memory profile your program - it might be that, when you are creating new Board instances, the previous instances will be "hanging" and not garbage collected resulting into potential memory leaks
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.