15퍼즐

n2=[0,3,12,15]

n3=[1,2,4,7,8,11,13,14]

confdic={}

confdic[1]=[-1,1,4]

confdic[2]=[-1,1,4]

confdic[4]=[1,-4,4]

confdic[8]=[1,-4,4]

confdic[7]=[-1,-4,4]

confdic[11]=[-1,-4,4]

confdic[13]=[-1,1,-4]

confdic[14]=[-1,1,-4]

def next(al):

    i=0

    nl=[]

    while al[i]>0: i=i+1

    if i in n2:

        d=-1

        if i in [0,12]: d=1

        bl=al[:]

        bl[i],bl[i+d]=al[i+d],al[i]

        nl.append(bl)

        d=-4

        if i in [0,3]: d=4

        bl=al[:]

        bl[i],bl[i+d]=al[i+d],al[i]

        nl.append(bl)

    elif i in n3:

        tl=confdic[i]

        for x in tl:

            bl=al[:]

            bl[i],bl[i+x]=bl[i+x],bl[i]

            nl.append(bl)

    else:

        for x in [-1,1,-4,4]:

            bl=al[:]

            bl[i],bl[i+x]=bl[i+x],bl[i]

            nl.append(bl)

    return nl

            

def try2find(start,end):

    q=[start]

    visit=[]

    while q:

        if len(q)%1000==0:

            print '#',

        x=q.pop(0)

        #print x

        yl=next(x)

        for y in yl:

            if y in visit: pass

            else: 

                visit.append(y)

                q.append(y)

                if y[:4]==end:

                    print '*** gotit ***'

                    raw_input()

try2find([10,3,7,5,11,8,12,13,1,15,2,4,9,14,0,6],[1,2,3,4])