title: Python implementation of BFS to solve 8-puzzle takes too long to find a solution
body: <p>My implementation of BFS in Python to solve the 8-puzzle is taking at least 21 minutes to find a solution. How can I improve my code in order to achieve a better time? 
  The way I've implemented is very inefficient. I'd like to know any advice about how can I improve it in a way to solve in an acceptable time.</p>
  
  <pre class="lang-py prettyprint-override"><code>class Node():
      def __init__(self, board=[]):
          self.board=board
          self.adjacency_list=[]
  
      def get_adjacency_list(self):
          return self.adjacency_list
  
      def set_adjacency_list(self, adjacency_list):
          self.adjacency_list = adjacency_list
  
      def add_item_to_adjacency_list(self, item):
          self.adjacency_list.append(item)
  
      def generate_adjacency_list(self):
          '''
          Generates the adjancency list
          from a given puzzle 8's board.
          '''
          adj_lists = []
          empty_cell = 0
          row_empty_cell = col_empty_cell = 0
          tmp_array = None
  
          for array in self.board:
              if empty_cell in array:
                 tmp_array = array
                 break
          row_empty_cell = self.board.index(tmp_array)
          col_empty_cell = tmp_array.index(empty_cell)
  
          left = (row_empty_cell, col_empty_cell - 1)
          right = (row_empty_cell, col_empty_cell + 1)
          up = (row_empty_cell - 1, col_empty_cell)
          down = (row_empty_cell + 1, col_empty_cell)
          max_bound = 3
  
          for direction in [left, up, right, down]:
              (row, col) = direction
              if row &gt;= 0 and row &lt; max_bound and col &gt;= 0 and col &lt; max_bound:
                  adj_list = [r[:] for r in self.board]
                  adj_list[row_empty_cell][col_empty_cell] = adj_list[row][col]
                  adj_list[row][col] = empty_cell
                  self.add_item_to_adjacency_list(Node(adj_list))
  
  def bfs(root_node, goal_node):
      '''
      Implementation of the Breadth
      First Search algorithm.
      The problem to be solved by this
      algorithm is the Puzzle 8 game.
  
      input: root -- the root node where
      the search begins.
      goal_node -- The objective to reach.
  
      return:
      (path, node) -- A tuple with a
      dictionary path whose key node
      gives the path backwards to the
      objective node.
      '''
      frontier = [root_node]
      path = {root_node : None} # The path where a node came from
      level = {root_node : 0}
      boards = [root_node.get_board()] # List of boards to check a board was already generated
      i = 1
      while frontier:
          next_frontier = []
          for node_parent in frontier:
              if node_parent.get_board() == goal_node.get_board():
                  return (path, node_parent)
              node_parent.generate_adjacency_list()
              for children in node_parent.get_adjacency_list():
                  if children.get_board() not in boards:
                      boards.append(children.get_board())
                      next_frontier.append(children)
                      level[children] = i
                      path[children] = node_parent
          frontier = next_frontier
          print("Level ", i)
          print("Number of nodes ", len(frontier))
          i += 1
      return (path, root_node)
  
  root_node = Node([[2, 6, 0],
                    [5, 7, 3],
                    [8, 1, 4]])
  
  goal_node = Node([[1, 2, 3],
                    [4, 5, 6],
                    [7, 8, 0]])
  
  import time
  start = time.time()
  
  path, node =  bfs(root_node, goal_node)
  
  end = time.time()
  print(end - start)
  </code></pre>