[技术交流] python小练习（064）：探索法（广度优先搜索）不到40行代码求解拼图游戏的最优路径

#red:0 blue:1 white:2.     4*3
begin=(2,0,1,1,0,0,1,1,0,0,1,1)
end=(2,1,0,1,1,0,1,0,0,1,0,1)
move=[(0,-1),(0,1),(1,0),(-1,0)]
step={}
st=[end]
s=st.pop()
sss=[end]
def check(x):
    if tuple(x) not in sss:
        st.append(tuple(x))
        step[tuple(x)]=s
        sss.append(tuple(x))
def twol(y):
    global i
    for j in range(12):
        if y[j]==2:
            i=j
while s!=begin:
    a,b,c,d=list(s),list(s),list(s),list(s)
    for mo in move:        
        if mo==(0,-1):
            twol(a)
            if a[i] not in a[0:12:4]:
                a[i],a[i-1]=a[i-1],a[i]
                check(a)
        elif mo==(0,1):
            twol(b)
            if b[i] not in b[3:12:4]:
                b[i],b[i+1]=b[i+1],b[i]
                check(b)
        elif mo==(1,0):
            twol(c)
            if c[i] not in c[8:12]:
                c[i],c[i+3]=c[i+3],c[i]
                check(c)
        elif mo==(-1,0):
            twol(d)
            if d[i] not in d[0:4]:
                d[i],d[i-3]=d[i-3],d[i]
                check(d)
    s=st.pop(0)
    if len(st)==0:
        print("no solution!")
        break
else:
    sa=begin
    print("start!!")
    print(sa)
    while sa!=end:
        sa=step[sa]
        print(sa)