Python implementation of BFS to solve 8-puzzle takes too long to find a solution

Question

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.

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 >= 0 and row < max_bound and col >= 0 and col < 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)

Answer 1

I think that the problem is in this line:

 if children.get_board() not in boards:

This is a linear search, try to change this to binary search.

Answer 2

Use a heuristic, like A*. This is known to work well and there are many guides on it.