Larghezza Di Ricerca Prima Di Loop Infinito

Sto creando il 8 AI puzzle game in bfs e si finisce sempre in un ciclo infinito , io sto usando una coda per memorizzare il esplorato (non ancora visitato nodi) , e una lista per memorizzare il esplorato e nodi visitati di evitare di visitare lo stesso stato più volte , anche im utilizzando getNextStates() funzione per ottenere tutti i possibili stati successivi a seconda della posizione di "0" , switch() è responsabile per la creazione di una nuova , il mio codice :

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