使用Python使用BFS算法解决8难题

Question

我想用bfs算法并使用Python解决8难题的问题这是我的代码，我不明白我的代码到底是什么问题。但是它一直在运行，并且不会停止并且无法解决问题。

list = [1,2,3,8,0,4,7,6,5]
goal_list=[2,8,1,0,4,3,7,6,5]
for i in list:
    if list[i]==0:
        x=i
print(x)

count=0
check="false"
list_up=[]
list_down=[]
list_left=[]
list_right=[]
list_copy=[]
queue=[]
save_list=[]


up=x-3
down=x+3
left=x-1
right=x+1

if up>=0:

    list_up=list.copy()
    list_up[x]=list_up[up]
    list_up[up]=0
    u=up
    up=u-3
    count+=1
    queue.append(list_up)
    save_list.append(list_up)
    print (queue)
    if list_up==goal_list:
        #check=true
        print("problem solved with %d tries" %count)

if down<=8:
    list_down=list.copy()
    list_down[x]=list_down[down]
    list_down[down]=0
    count+=1
    d=down
    down=d+3
    queue.append(list_down)
    save_list.append(list_down)
    if list_down==goal_list:
        print("problem solved with %d tries" %count)

if left>=0:
    list_left=list.copy()
    list_left[x]=list_left[left]
    list_left[left]=0
    count+=1
    l=left
    left=l-1
    queue.append(list_left)
    save_list.append(list_left)
    if list_left==goal_list:
        print("problem solved with %d tries" %count)

if right<=8:
    list_right=list.copy()
    list_right[x]=list_right[right]
    list_right[right]=0
    count+=1
    r=right
    right=r+1
    queue.append(list_right)
    save_list.append(list_right)
    print("in if right")
    if list_right==goal_list:
        print("problem solved with %d tries" %count)
    #print(queue.pop(0))    


def go_up():
    global up
    global u
    global count
    global check
    global queue
    global list_up
    global save_list
    global goal_list
    print("in up def")
    for i in list_up:
        if list_up[i]==0:
            u=i
            up=u-3
    if up>=0:
        list_up[u]=list_up[up]
        list_up[up]=0
        count+=1
        #u=up
        #up=u-3
        queue.append(list_up)
        save_list.append(list_up)
        if list_up==goal_list:
            check="true"
            print("problem solved with %d tries" %count)
            print(save_list)


def go_down():
    global down
    global d
    global count
    global check
    global queue
    global list_down
    global save_list
    global goal_list
    for i in list_down:
        if list_down[i]==0:
            d=i
            down=d+3
    if down<=8:
        print("in down def")
        #list_down=list.copy()

        list_down[d]=list_down[down]
        list_down[down]=0
        count+=1
        d=down
        down=d+3
        queue.append(list_down)
        save_list.append(list_down)
        if list_down==goal_list:
            check="true"
            print("problem solved with %d tries" %count)
            print(save_list)


def go_left():
    global left
    global l
    global count
    global check
    global queue
    global list_left
    global save_list
    global goal_list
    for i in list_left:
        if list_left[i]==0:
            l=i
            left=l-1
    if left>=0:
       #if l not in[0,3,6] :
        if l==1|l==2|l==4|l==5|l==8|r==7:
           print("in left def")

           #list_left=list.copy()
           list_left[l]=list_left[left]
           list_left[left]=0
           count+=1
           l=left
           left=l-1
           queue.append(list_left)
           save_list.append(list_left)
           if list_left==goal_list:
               check="true"
               print("problem solved with %d tries" %count)
               print(save_list)


def go_right():
    global right
    global r
    global count
    global check
    global queue
    global list_right
    global save_list
    global goal_list
    for i in list_right:
        if list_right[i]==0:
            r=i
            right=r+1
    if right<=8:
        #if r not in[2,5,8]:
        if r==0|r==1|r==3|r==4|r==6|r==7:
            print("in right def")

            list_right[r]=list_right[right]
            list_right[right]=0
            count+=1
            r=right
            right=r+1
            queue.append(list_right)
            save_list.append(list_right)
            if list_right==goal_list:
                check="true"
                print("problem solved with %d tries" %count)
                print(save_list)



while check=="false":
    print("len queue is:")
    print(len(queue))
    if len(queue)>0:
        list_copy=queue.pop(0)
        print (len(queue))
        list_up=list_copy.copy()
        go_up();
        if check=="true":
            break


        list_down=list_copy.copy()
        go_down();
        if check=="true":
            break
        list_left=list_copy.copy()
        go_left();
        if check=="true":
            break
        list_right=list_copy.copy()
        go_right();
        if check=="true":
            break


print("out of while")
print (save_list)
print ()

我是python新手，将不胜感激

关于我的代码：list拥有初始状态，goal_list是最终状态。我设置检查变量以检查是否达到了最终目标。 x，u，d，l，r在列表中保留索引0。 save_list是到达最终状态所经历的溃败代码。

再次感谢您的帮助

Answer 1

这不是一个完整的答案，但我可以立即发现一些问题。有这样的声明：

if r==0|r==1|r==3|r==4|r==6|r==7

它们不像您认为的那样工作。阅读Python中的逻辑运算符链接。例如，对于r == 1，此表达式实际上评估为False。

您与您注释掉的陈述更加接近：

#if r not in[2,5,8]:

应该是：

if r not in (2, 5, 8):

in运算符后必须有一个空格。

请勿将“列表”用作变量名，因为它是Python中的内置类，其使用可能导致细微的错误。队列也不是变量名的好选择，因为有多个标准库模块使用此名称。

您应该在任何语言中少量使用全局变量。

最后，我有一个友善的建议：我认为通过输入230行复杂代码然后在无法使用时举起手来学习一种新语言不是一个好主意。您可以用一种新语言编写那么多无错误代码的机会，必须与明天不会出现太阳的机会接近零。从一个较小的问题开始。