# 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.