Largura Primeira Pesquisa Loop Infinito

Eu estou criando a 8 de quebra-cabeça jogo AI em bfs e que sempre acaba em um loop infinito , eu estou usando uma fila para armazenar o explorado (ainda não visitei a nós) , e uma lista para armazenar os explorados e visitados nós para evitar que visitar o mesmo estado várias vezes , também estou usando getNextStates() função para obter todos os possíveis estados seguintes, dependendo da posição de "0" , " switch() é responsável por criar o próximo estado , o meu código :

goalState=[0, 1, 2, 3, 4, 5, 6, 7, 8]
def switch(list,index1,index2):
    newList=[]
    for i in range(len(list)):
        newList.append(list[i])

    temp=newList[index1]
    newList[index1]=newList[index2]
    newList[index2]=temp
    return newList

def getNextStates(state):
    nextStates=[]
    length=len(state)
    emptyTile=0
    for i in range(length):
        if state[i]==0:
            emptyTile=i
            #    1
            # 0  3
    print('empty tile in position : ' , emptyTile)
    if emptyTile==0:
        nextStates.append(switch(state,0,1))
        nextStates.append(switch(state, 0, 3))
    elif emptyTile==1:
        nextStates.append(switch(state, 1, 0))
        nextStates.append(switch(state, 1, 4))
        nextStates.append(switch(state, 1, 2))
    elif emptyTile==2:
        nextStates.append(switch(state, 2, 1))
        nextStates.append(switch(state, 2, 5))
    elif emptyTile==3:
        nextStates.append(switch(state, 3, 0))
        nextStates.append(switch(state, 3, 4))
        nextStates.append(switch(state, 3, 6))
    elif emptyTile==4:
        nextStates.append(switch(state, 4, 3))
        nextStates.append(switch(state, 4, 1))
        nextStates.append(switch(state, 4, 5))
        nextStates.append(switch(state, 4, 7))
    elif emptyTile==5:
        nextStates.append(switch(state, 5, 2))
        nextStates.append(switch(state, 5, 4))
        nextStates.append(switch(state, 5, 8))
    elif emptyTile==6:
        nextStates.append(switch(state, 6, 3))
        nextStates.append(switch(state, 6, 7))
    elif emptyTile==7:
        nextStates.append(switch(state, 7, 6))
        nextStates.append(switch(state, 7, 4))
        nextStates.append(switch(state, 7, 8))
    else:
        nextStates.append(switch(state, 8, 7))
        nextStates.append(switch(state, 8, 5))

    return nextStates


def breadthFirst(initialState,goal):
    global exploredCount , visitedCount
    exploredCount = 1
    visitedCount = 0
    frontier = []
    frontier.append(initialState)
    explored=[]
    print("Staring Dequing....")
    while len(frontier) > 0:
        print(len(frontier))
        state=frontier.pop(0)
        print("dequed : " , state)
        explored.append(state)
        print("appended in explored and visitedCount incremented")
        visitedCount += 1
        if state==goal:
            print("State Is Accomplished")
            return state
        nextStates=getNextStates(state)
        print("possible Next States : " , nextStates)
        for i in range(len(nextStates)):
            print('Checking Child states , current : ' , nextStates[i])
            if  not nextStates[i] in explored:
                if not nextStates[i] in frontier:
                    print("not in visited or explored , enqueue")
                    frontier.append(nextStates[i])
                    exploredCount += 1
 
    return initialState