import numpy as np
from collections import Counter
import copy
import time
def standardFif():
'''标准的十五数码'''
data = [[3,0,6],[1,8,5],[4,7,2]]
return data
def creatFif():
''''构建并返回十五数码'''
data = [[],[],[],[],0,0]#存十五数码,第一个0存深度，第二个0存当前状态（0：初始状态；1：0上移得来；2：0下移得来；3：0左移得来；4：0右移得来）
i = 0
while(i<16):
j = eval(input('输入第'+str(i+1)+'个数据：'))
if 0<=j<=15:
data[int(i/4)].append(j)
i = i+1
else:
print('输入数据错误!\n')
return data
def findLocation(data,findNum):
data_array=(data[:4])
return (data_array==findNum)[0]
def errorNum(data_1,data_2):
errorNum = 0
loc_1 = findLocation(data_1,0)
loc_2 = findLocation(data_2,0)
for i in range(4):
for j in range(4):
if data_1[i][j] != data_2[i][j]:
errorNum = errorNum + 1
if loc_1[0]==loc_2[0 and loc_1[1]==loc_2[1]]:
return errorNum
else:
return errorNum-1
def getReverseOrderNumber(list):
'''获得逆序数'''
num = 0
for i in range(1,len(list)):
for j in range(i):
if list[j]>list[i]:
num = num+1
return num
def judge(data_1,data_2):
'''判断两个十五数码是否可互相到达（逆序奇偶性）'''
temp1 = (data_1[0:4])
temp2 = (data_2[0:4])
list1 = sum(temp1, [])
list2 = sum(temp2, [])
(0)
(0)
if getReverseOrderNumber(list1)%2==getReverseOrderNumber(list2)%2:
return True
else:
print("无解！")
return False
'''构建估价函数'''
def aStarOne(data_1,data_2):
'''十五数码错放棋子个数的估价函数'''
'''data_1:标准十五数码;data_2:构造的十五数码'''
return errorNum(data_1,data_2)+data_2[4]
'''errorNum = 0
for i in range(3):
for j in range(3):
if data_1[i][j] != data_2[i][j]:
errorNum = errorNum+1
return errorNum+data_2[3]-1'''
def aStarTwo(data_1,data_2):
'''错放棋子与目标位置距离之和构成的估价函数'''
errorDistance = 0
for i in range(1,16):
loc_1 = findLocation(data_1,i)
loc_2 = findLocation(data_2,i)
errorDistance = abs(loc_1[0]+loc_1[1]-loc_2[0]-loc_2[1])+errorDistance#求曼哈顿距离
return errorDistance+data_2[4]
'''构建移动函数'''
def up(data):
'''上移'''
zeroLoc = findLocation(data,0)
i = int(zeroLoc[0])
j = int(zeroLoc[1])
if i>0:
temp = data[i][j]
data[i][j] = data[i-1][j]
data[i-1][j] = temp
data[4] = data[4] + 1
data[5] = 1
return data
else:
return
def down(data):
'''下移'''
zeroLoc = findLocation(data, 0)
i = int(zeroLoc[0])
j = int(zeroLoc[1])
if i<3:
temp = data[i][j]
data[i][j] = data[i+1][j]
data[i+1][j] = temp
data[4] = data[4] + 1
data[5] = 2
return data
else:
return
def left(data):
'''左移'''
zeroLoc = findLocation(data, 0)
i = int(zeroLoc[0])
j = int(zeroLoc[1])
if j>0:
temp = data[i][j]
data[i][j] = data[i][j-1]
data[i][j-1] = temp
data[4] = data[4] + 1
data[5] = 3
return data
else:
return
def right(data):
'''右移'''
zeroLoc = findLocation(data, 0)
i = int(zeroLoc[0])
j = int(zeroLoc[1])
if j<3:
temp = data[i][j]
data[i][j] = data[i][j+1]
data[i][j+1] = temp
data[4] = data[4] + 1
data[5] = 4
return data
else:
return
def overCondition(data,openTable):
'''判断目标十五数码是否在openTable中，
返回 True or False
并返回目标十五数码在openTable的索引
'''
index = -1
for item in openTable:
index = index + 1
j = 0
for i in range(4):
if item[i] == data[i]:
j = j + 1
if j == 4:
print("搜索成功！")
return True,index
return False,-1
def extend(data_1,data_2,openTable,valueTable,closeTable,mode,index2):
'''扩展十五数码,并将被扩展的十五数码移除出openTable'''
'''data_1:被扩展的十五数码；data_2:标准十五数码'''
if data_1[5]==0:
data1=up((data_1))
if data1:
(data1)
if mode == "1":
(aStarOne(data_2,data1))
else:
(aStarTwo(data_2, data1))
data2=down((data_1))
if data2:
(data2)
if mode == "1":
(aStarOne(data_2, data2))
else:
(aStarTwo(data_2, data2))
data3=left((data_1))
if data3:
(data3)
if mode == "1":
(aStarOne(data_2, data3))
else:
(aStarTwo(data_2, data3))
data4=right((data_1))
if data4:
(data4)
if mode == "1":
(aStarOne(data_2, data4))
else:
(aStarTwo(data_2, data4))
del valueTable[index2]
(data_1)
(data_1)
elif data_1[5]==1:
data1 = up((data_1))
if data1:
(data1)
if mode == "1":
(aStarOne(data_2, data1))
else:
(aStarTwo(data_2, data1))
data3 = left((data_1))
if data3:
(data3)
if mode == "1":
(aStarOne(data_2, data3))
else:
(aStarTwo(data_2, data3))
data4 = right((data_1))
if data4:
(data4)
if mode == "1":
(aStarOne(data_2, data4))
else:
(aStarTwo(data_2, data4))
del valueTable[index2]
(data_1)
(data_1)
elif data_1[5]==2:
data2 = down((data_1))
if data2:
(data2)
if mode == "1":
(aStarOne(data_2, data2))
else:
(aStarTwo(data_2, data2))
data3 = left((data_1))
if data3:
(data3)
if mode == "1":
(aStarOne(data_2, data3))
else:
(aStarTwo(data_2, data3))
data4 = right((data_1))
if data4:
(data4)
if mode == "1":
(aStarOne(data_2, data4))
else:
(aStarTwo(data_2, data4))
del valueTable[index2]
(data_1)
(data_1)
elif data_1[5]==3:
data1 = up((data_1))
if data1:
(data1)
if mode == "1":
(aStarOne(data_2, data1))
else:
(aStarTwo(data_2, data1))
data2 = down((data_1))
if data2:
(data2)
if mode == "1":
(aStarOne(data_2, data2))
else:
(aStarTwo(data_2, data2))
data3 = left((data_1))
if data3:
(data3)
if mode == "1":
(aStarOne(data_2, data3))
else:
(aStarTwo(data_2, data3))
del valueTable[index2]
(data_1)
(data_1)
elif data_1[5]==4:
data1 = up((data_1))
if data1:
(data1)
if mode == "1":
(aStarOne(data_2, data1))
else:
(aStarTwo(data_2, data1))
data2 = down((data_1))
if data2:
(data2)
if mode == "1":
(aStarOne(data_2, data2))
else:
(aStarTwo(data_2, data2))
data4 = right((data_1))
if data4:
(data4)
if mode == "1":
(aStarOne(data_2, data4))
else:
(aStarTwo(data_2, data4))
del valueTable[index2]
(data_1)
(data_1)
def flashBack(data,temp_closeTable):
'''从初始十五数码回溯至目标十五数码'''
print(data)
tempTable=[]
'''将上一层的十五数码移入tempTable'''
for item in temp_closeTable:
if item[4]==data[4]-1:
(item)
for item in tempTable:
if abs(errorNum(item,data))==1:
break
if item[4]==0:
print(item)
return
else:
flashBack(item,temp_closeTable)
'''运行测试'''
#a=findLocation(standEight,0)
print("输入目标十五数码：")
standEight = creatFif()
print("输入初始十五数码")
testEight = creatFif()
print("\n")
start_time=time.perf_counter()
if judge(testEight,standEight):
mode = input("请选择估价函数(1 or 2):")
if mode not in ["1","2"]:
print("模式选择错误，没有选择正确的估价函数！")
else:
openTable=[testEight]
closeTable=[]
valueTable=[aStarOne(standEight,testEight)]
while 1:
flag,index1 = overCondition(standEight,openTable)
if flag:
print("搜索路径如下：")
temp_closeTable = (closeTable)
flashBack(openTable[index1],temp_closeTable)
#print(openTable[index1])
#print(openTable)
#print(closeTable)
break
minNum = min(valueTable)
temp_list = []
for i in range(len(valueTable)):
if valueTable[i] == minNum:
temp_list.append(openTable[i])
for i in range(len(temp_list)):
index2 = (temp_list[i])
extend(temp_list[i], standEight, openTable, valueTable, closeTable, mode, index2)
end_time=time.perf_counter()
print("扩展的节点个数{}".format(len(openTable)+len(closeTable)))
print("运行时间：{}".format(end_time-start_time))