Demo entry 6655759

gg

   

Submitted by anonymous on Oct 28, 2017 at 06:29
Language: Python 3. Code size: 3.4 kB.

#-----A*算法解16宫格------#
import copy

def myprint(x):
    for i in range(4):
        print('')
        for j in range(4):
            print(x[i][j],'\t',end='')
    print('')

def myinput():
    x=[[0]*4]*4
    for i in range(4):
        x[i]=input().split(' ')
    for i in range(4):
        for j in range(4):
            x[i][j]=int(x[i][j])
    return x

openset = []
closedset = []
tempset = []
goal=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]
print('请输入初始状态:')
now=myinput()
print('目标结果为')
myprint(goal)

def output(n):
    print('最优路径到目标位置需要',n.deep,'步')
    if n.deep!=0:
        k=1
        while n.path[k]!=-1:
            print('第',k,'步')
            for i in range(4):
                if 0 in now[i]:
                    j = now[i].index(0)
                    break
            move(now,i,j,n.path[k])
            myprint(now)
            print('-----------------------------')
            k=k+1
    else:
        print('初始状态和目标状态一致')

def expend(now,goal):
    cost=0
    for a in range(15):
        for i1 in range(4):
            if a in now[i1]:
                j1=now[i1].index(a)
                break
        for i2 in range(4):
            if a in goal[i2]:
                j2=goal[i2].index(a)
                break
        cost=cost+abs(i1-i2)+abs(j1-j2)
    return cost
        
class Node(object):
    def __init__(self,deep,path,x):
        self.deep = deep
        self.path= path
        self.x= x
        self.distance = expend(self.x,goal) + self.deep

def equal(a,b):
    for i in range(4):
        for j in range(4):
            if a[i][j] != b[i][j]:
                return False
    else:
                return True

def move(n,i,j,direction):
    if ((i==0 and direction==0)or(i==3 and direction==1)or(j==0 and direction==2)or(j==3 and direction==3)):
        return 0
    elif direction == 0:
        temp = n[i][j]
        n[i][j] = n[i-1][j]
        n[i-1][j] = temp
    elif direction == 1:
        temp = n[i][j]
        n[i][j] = n[i+1][j]
        n[i+1][j] = temp
    elif direction == 2:
        temp = n[i][j]
        n[i][j] = n[i][j-1]
        n[i][j-1] = temp
    elif direction == 3:
        temp = n[i][j]
        n[i][j] = n[i][j+1]
        n[i][j+1] = temp
    return 1


def main():
    path = [-1]*65535
    inti=Node(0,copy.deepcopy(path),copy.deepcopy(now))
    openset.append(inti)
    while  openset:
        value=[]
        for m in range(len(openset)):
            value.append(openset[m].distance)
        mi = value.index(min(value))
        n = openset[mi]
        openset.pop(mi)
        closedset.append(copy.deepcopy(n.x))
        if equal(n.x,goal):
            output(n)
            break
        else:
            for i in range(4):
                if 0 in n.x[i]:
                    j = (n.x[i]).index(0)
                    break
            for direction in range(4):
                if move(n.x,i,j,direction):
                    temppath=copy.deepcopy(n.path)
                    temppath[n.deep+1] = direction
                    new=Node(copy.deepcopy(n.deep)+1,copy.deepcopy(temppath),copy.deepcopy(n.x))
                    tempset.append(new)
                    move(n.x,i,j,direction)
                    if new.x not in closedset:
                        openset.append(new)
                    move(n.x,i,j,direction)
main()

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).