Python A-Star 8谜题输出问题

我正在研究一个A-Star算法来解决8道难题。我的大部分算法都失败了，但我在输出方面遇到了问题。它可以很好地解决这个问题[0，1，2，3，8，4，6，7，5]，但当涉及到更复杂的问题时，例如[6，4，0，1，5，3，7，8，2]，它一直在同一条路径上循环，似乎没有找到解决方案。如果你能给我指导或指出我哪里出错了，请帮忙。非常感谢。

代码如下：

from math import sqrt
import time
#fring- to keep the nodes 
#expand: the function to expand one node at a time 
    #heuristic: calculate the cheapest cost
    #f()- total cost 
    #h()- the number index to the goal 
#expanded_nodes- have all the visited 
startime = time.time_ns()
def astar(puzzle):
    
    #intializing the variables 
    cost = 0
    node = Node(puzzle,cost)
    loop = True
 
    #the possible nodes  
    fringe = []  
    #After expanding the list 
    expanded = []

    # maybe need it keep it for now 
    visit = set() #keep track of all the visit 
    
    #the goal state
    goal = [0,1,2,3,4,5,6,7,8] 
    
    #possible combination move
    possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
   
   
   
    #intialization of the first node 
    fringe = [node]
    #print('state:'+str(node.state))
    
    
 
    
    #start the loop 
    while loop:
        print('\nthe state of this game position is:\n ' + str(node.state) +"\n\n")
        
        #find the lowest cost in the fringe then expand the lowest cost node
        min_cost = fringe[0].cost 
        min_node = fringe[0]
        
        for node in fringe[:]:
            if node.cost < min_cost:
                min_cost = node.cost
                min_node = node
                
        #append the node that was just expaneded into the expanded list but keep the list not expaneded in fringe 
        expanded.append(min_node)
        print('the min node '+str(min_node.state)+'\nthe cheapest cost: '+ str(min_cost))
       
        #removes the min cost node from fringe  
        for node in fringe[:]:
            if node.state == min_node.state:
                fringe.remove(node)
        
        #when there is a solution in the expanded 
        for node in expanded:
            if node.state == goal:
                loop = False
       
        #traverse the nodes that was expanded and add the children to the fringe 
        for node in expanded[:]:
          
            #append all the successor/children and set the children's parent to fringe 
            blank = node.state.index(8)
            print('the index of the blank is '+ str(blank))
            print('\n')
            possible_pos = possible_move[blank]
            print('possible pos '+ str(possible_pos))
                
            for i in possible_pos:
                    
                    print('\n')
                    possible_sw = node.state[:]
                    print('index swap = '+ str(i))
                    possible_sw[blank] = possible_sw[i]
                    possible_sw[i] = 8
                    print('the child node is ' + str(possible_sw))
                    node.cost = manhattan(possible_sw, goal)
                    fringe.append(Node(possible_sw,node.cost,node))
                    print('the cost this node state: '+ str(node.cost)) 
        expanded.pop(0)

    #finding the solution  
    move = 0
    while node.parent:
        
        expanded.append(node.state.index(8))
        node = node.parent
        move += 1
    print('moves made '+ str(move))
   
    

    expanded.reverse()
    print('moves list '+ str(expanded))
    endtime = time.time_ns()
    executionTime = ( endtime - startime)
    print('Execution time in ns: ' + str(executionTime))
    return expanded     

#Try the Manhattan Distance
def manhattan(a, b):
        return sum(abs(val1-val2) for val1, val2 in zip(a,b))

class Node:
    def __init__(self,state,cost,parent = None):
        self.parent = parent
        self.state = state
        self.cost = cost
        self.children = []


#test case 
p = [0, 1, 2, 3, 4, 5, 6, 8, 7]
p = [0, 1, 2, 3, 8, 4, 6, 7, 5]
#p= [6, 4, 0, 1, 5, 3, 7, 8, 2]
#p = [1, 8, 2, 0, 3, 5, 6, 4, 7]
print("++++++++++A*++++++++++++")
astar(p)