How can I increase my BFS speed when solving the 8-puzzle problem?

I am implementing BFS for a project. I am trying to solve the 8 puzzle game. I tested my BFS implementation on simpler inputs such as the following and it works:

Input State: [1, 2, 5, 3, 4, 8, 6, 7, 0] Goal State: [0, 1, 2, 3, 4, 5, 6, 7, 8]

This leads me to think that more complex solutions are not solving fast because my code is slow.

Here are a few things to note about my code.

• Each board state is contained in a board object from the board class.
• My BFS saves the parent board state so I can map the path once I find the solution.

My thoughts about why it is slow:

• I am using pop() in my frontier queue.
• I was searching through all of the visited nodes to compare to the newly created child node to see if it was in the visitedStates list so I could not add it to the frontier. I assume this was an O(n) search and my visitedStates list gets very large. I changed that list to a set because as far as I know sets in Python are on average O(1) for lookup. I then contemplated on the time difference between doing those extra searches and removing them with the comparison.
• Maybe looking up the values from all the Board objects is slowing it down?

Any ideas on how I can speed up my BFS code?

BFS function:

def breadthFirstSearch(startState, endState):
#Set of states that have being visited from the graph.
visitedStates = set()
#Queue of states to be visted. This is our frontier.
frontier = [startState]

while frontier:
    #Pop the current state from the head of the queue.
    currentState = frontier.pop(0)
    #Add the current child to the visited states list.
    visitedStates.add(currentState)

    #Compare the currentState's state to the goalState.
    if currentState.state == endState:
        #Solution found.
        #print(str(currentState.state))
        #print("Depth: " + str(visitedStates[-1].depth))
        print("Depth: " + str(currentState.depth))
        return currentState.state

    #Generate the childs children so the search can continue. 
    #This creates a part of the next layer of the tree.
    currentState.generateChildList()
    #print("\nCurrent State: " + str(currentState.state))
    #if currentState.parent is not None:
    #   print("Parent State: " + str(currentState.parent.state))

    #This loop peeks at each of the current states neighbors and decides if they have
    #being visited yet. If they have not being visited then they are added to the queue.
    for child in currentState.childrenList:
        if child not in visitedStates:
            frontier.append(child)

    setNodeParents(currentState, currentState.childrenList)

#Print the depth.
print("Depth: " + str(currentState.depth))
steps = len(visitedStates)
return currentState.state, steps

EDIT: I noticed that I use pop() a lot. I am thinking that implementing a deque from collections.deque will speed up the popping operation a lot. Only issue is I cant figure out how to add a deque of class objects. Maybe a dictionary?

The solution to my issue was to turn my boards from lists into tuples and change my visitedStates list to a set that contains tuples. This made my program tremendously fast.