8 puzzle implementation

driver3.py

import time
import resource
from collections import deque
# Global Constants
DIMENSIONS = 3
DIRECTIONS = {"U": -1, "D": 1, "L": -1, "R": 1}
UPPER_BOUND = 0
LEFT_BOUND = 0
DOWN_BOUND = DIMENSIONS - 1
RIGHT_BOUND = DIMENSIONS - 1
GOAL_STATE = ["0", "1", "2", "3", "4", "5", "6", "7", "8"]
#ALGORITHMS  = { "BFS" : bfs, "DFS": dfs, "AST": ast}
# Queue class


class Node:
  def __init__(self, state, path):
    self.state = State(state)
    self.path = path

  def __eq__(self, other):
    return self.state == other.state

  def __ne__(self, other):
    return not self.__eq__(self, other)

  def __hash__(self):
    return hash(self.state)


class State:

  def __init__(self, state_string):

    self.matrix = state_string

  def __eq__(self, other):
    return self.matrix == other.matrix

  def __ne__(self, other):
    return not self.__eq__(self, other)

  def __str__(self):
    return "".join(self.matrix)

  def __hash__(self):
    return hash(str(self))

  def neighbors(self):
    u = [self.move("U"), "Up"]
    d = [self.move("D"), "Down"]
    l = [self.move("L"), "Left"]
    r = [self.move("R"), "Right"]
    return [u, d, l, r]

  def move(self, direction):
    idx = self.get_empty()
    new_idx = self.idx_move(direction, idx)
    if new_idx is None:
      return None

    new_m = self.matrix[:]
    temp = new_m[idx + new_idx]
    new_m[idx + new_idx] = "0"
    new_m[idx] = temp
    return new_m

  def idx_move(self, direction, idx):
    if direction == "U" and idx not in (0, 1, 2):
        return -3
    elif direction == "D" and idx not in (6, 7, 8):
        return 3
    elif direction == "L" and idx not in (0, 3, 6):
        return -1
    elif direction == "R" and idx not in (2, 5, 8):
        return 1
    else:
        return None

  def get_empty(self):  # O(1)? O(n)? O(len(x) + len(y))
    return self.matrix.index("0")


class Search:
  def __init__(self, goal_test):
    self.goal_test = goal_test

  def get_depth(self, node):
    return len(self.get_path(node))

  def get_path(self, node):
    return node.path

  def bfs(self, initial_state):
    node = Node(initial_state, [])
    frontier = deque()
    explored = set()
    frontier.append(node)

    while len(frontier) > 0:
      node = frontier.popleft()
      explored.add(node)
      if(self.goal_test(node.state.matrix)):
        return {
            "status": "success",
            "frontier": frontier,
            "explored": explored,
            "depth": len(self.get_path(node)),
            "path": self.get_path(node)
        }
      for neighbor in node.state.neighbors():
        if neighbor[0]:
          new_path = node.path[:]
          new_path.append(neighbor[1])
          new_node = Node(neighbor[0], new_path)
          if new_node not in explored:
            frontier.append(new_node)
    return {
        "status": "fail",
        "frontier": frontier,
        "explored": explored
    }


def goal_test(state):
  return GOAL_STATE == state


start_time = time.time()
#i = "1,2,5,3,4,0,6,7,8"
#i = "6,1,8,4,0,2,7,3,5"
i = "8,6,4,2,1,3,5,7,0"
arr_state = i.split(",")
search = Search(goal_test)
stats = search.bfs(arr_state)
elapsed_time = time.time() - start_time
print("path_to_goal", stats.get('path'))
print("cost_of_path", stats.get('depth'))
print("nodes_expanded", len(stats.get('explored')) - 1)
print("search_depth", stats.get('depth'))
print("max_search_depth", max([search.get_depth(node)
                               for node in stats.get('frontier')]))
print("running_time", elapsed_time)
print(resource.getrusage(resource.RUSAGE_SELF).ru_maxrss / 1024, 'MB')
print("max_ram_usage", resource.getrusage(resource.RUSAGE_SELF).ru_maxrss)

https://gist.github.com/bialikover/60dec249431b81dceb348fb702720e9a#file-driver3-py-L111

for neighbor in node.state.neighbors():
        if neighbor[0]:
          new_path = node.path[:]
          new_path.append(neighbor[1])
          new_node = Node(neighbor[0], new_path)
          if new_node not in explored:
            frontier.append(new_node)

Aqui si solo vas por el primer elemento porque usas el for? no seria mas sencillo solo hacer if node.state.neighbors()[0] ? te ahorras un for sobre todo si la lista tiene mas elementos, el for los va a ejecutar todos aunque solo uses uno.

La idea es checar cada uno de los neighbors que no sean None y ver si ya esta en el explored set y si no entonces ponerlo en el frontier queue.

Creo que si esta un poco ilegible esa parte