如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。

 思路：广度遍历+剪枝

#!/usr/bin/env python
# coding: utf-8
 
# In[15]:
 
 
def cmp(a,b): #比较是否一致
    if a==b:
        return 1
    return 0
def getsite(A):#得到.的位置，下标
    t=0
    for i in A:
        if i=='.':
            return t
        t+=1
 
def getP(A,B,finds,):#A是当前状态，finds里记录已经遍历过的状态
    t=getsite(A)  #得到下标
    Next=set()    #广度优先遍历的对垒，我用的集合来实现访问元素的存储
    if t%3>0:     #判断能够往哪个方向走
        a=A.copy()
        temp=a[t-1]
        a[t]=temp
        a[t-1]='.'
        if ''.join(a) not in finds:   #如果不在状态记录集合finds里，则加入到里面
            finds.add(''.join(a))
            Next.add(''.join(a))      #为下一轮广度遍历准备
        if ''.join(a)==B:             #移动后发现和结束状态end一样，则结束，返回1
            return 1
    if t%3<2:      #判断能够往哪个方向走
        a=A.copy()
        temp=a[t+1]
        a[t]=temp
        a[t+1]='.'
        if ''.join(a) not in finds:
            finds.add(''.join(a))
            Next.add(''.join(a))
        if ''.join(a)==B:
            return 1
    if t/3>1:      #判断能够往哪个方向走
        a=A.copy()
        temp=a[t-3]
        a[t]=temp
        a[t-3]='.'
        if ''.join(a) not in finds:
            finds.add(''.join(a))
            Next.add(''.join(a))
        if ''.join(a)==B:
            return 1
    if t/3<2:       #判断能够往哪个方向走
        a=A.copy()
        temp=a[t+3]
        a[t]=temp
        a[t+3]='.'
        if ''.join(a) not in finds:
            finds.add(''.join(a))
            Next.add(''.join(a))
        if ''.join(a)==B:
            return 1
    return Next
 
def main(start,end):
    A=list(start)  #初始状态
    B=end        #最终状态
    finds=set()    #遍历过的状态，存储一下
    Next_path=getP(A,B,finds)  #先入队，或者入集合，方便广度遍历
    c=1            #记录路径长度，默认是1
    while(Next_path):#是否能够继续移动. 集合为空说明不能在移动了，状态都遍历过了
        S1=set()     #当前要入队，准备广度遍历的状态
        c+=1
        for i in Next_path:   #广度遍历
            #print(i)
            s=getP(list(i),B,finds)  #i状态下的的广度一轮遍历
            if s==1:               #如果返回的1则说明找到了
                return c
            else:                  #还没找到，准备下一轮遍历，将下一轮的状态集合合并
                #print('s',s)
                S1=S1|s
        Next_path=S1               #更新广度遍历的候选状态
    return -1
#main('12345678.','123.46758')
#main('12345678.','152743.86') #测试一
#main('12345678.','12356.784') #测试二
#main('2315.6784','8235164.7') #测试三
#main('13524678.','46758123.') #测试四
#main('12345678.','87654321.') #测试五
main('.87654321','12345678.') #测试六