|
|
# 目标序列end = [1,2,3,8,0,4,7,6,5]
|
|
|
# end = 1 2 3
|
|
|
# 8 0 4
|
|
|
# 7 6 5
|
|
|
import sys
|
|
|
|
|
|
|
|
|
class Statusobj:
|
|
|
def __init__(self):
|
|
|
# 状态序列
|
|
|
self.array = []
|
|
|
# 该状态下的深度
|
|
|
self.deep = 0
|
|
|
# 该状态的f(n) = g(n) + h(n)评估函数值
|
|
|
self.Fn = 0
|
|
|
# 该状态由上一个状态经何种操作得到，避免出现死循环
|
|
|
# 1:up 2:down 3:left 4:right
|
|
|
self.preoperate = 0
|
|
|
self.Father = Statusobj
|
|
|
|
|
|
|
|
|
# 判断八数码问题是否有解，在于若两个状态的逆序奇偶性 相同，则可相互到达，否则不可相互到达
|
|
|
def getreversenum(array): # 获取当前状态的逆序数和
|
|
|
count = 0
|
|
|
for i in range(len(array)):
|
|
|
for j in range(i+1, len(array)):
|
|
|
if array[j] < array[i]:
|
|
|
count += 1
|
|
|
return count
|
|
|
|
|
|
|
|
|
def countnotinplace(array, end): # 统计当前状态和目标状态相比较的不在位将牌数
|
|
|
count = 0
|
|
|
for i in range(len(array)):
|
|
|
if array[i] != end[i] and array[i] != 0:
|
|
|
count += 1
|
|
|
return count
|
|
|
|
|
|
|
|
|
def selectoperate(i, preoperate): # 通过当前状态下的序列下标和上一次操作符得到可选择的操作
|
|
|
selected = []
|
|
|
if 3 <= i <= 8 and preoperate != 2:
|
|
|
selected.append(1)
|
|
|
if 0 <= i <= 5 and preoperate != 1:
|
|
|
selected.append(2)
|
|
|
if i in [1, 2, 4, 5, 7, 8]:
|
|
|
if preoperate != 4:
|
|
|
selected.append(3)
|
|
|
if i in [0, 1, 3, 4, 6, 7]:
|
|
|
if preoperate != 3:
|
|
|
selected.append(4)
|
|
|
return selected
|
|
|
|
|
|
|
|
|
def op(i, x): # 通过操作符得到新下标
|
|
|
if i == 1: # up
|
|
|
return x-3
|
|
|
if i == 2: # down
|
|
|
return x+3
|
|
|
if i == 3: # left
|
|
|
return x-1
|
|
|
if i == 4: # right
|
|
|
return x+1
|
|
|
|
|
|
|
|
|
def newarray(operate, array): # 通过操作符拓展的新节点
|
|
|
subscript = array.index(0)
|
|
|
newindex = op(operate, subscript)
|
|
|
temp = array[subscript]
|
|
|
array[subscript] = array[newindex]
|
|
|
array[newindex] = temp
|
|
|
return array
|
|
|
|
|
|
|
|
|
def printarray(array):
|
|
|
print(f"{array[:3]}\n{array[3:6]}\n{array[6:]}\n", end='')
|
|
|
|
|
|
|
|
|
def main():
|
|
|
openlist = [] # open表，保存待扩展实例对象
|
|
|
closelist = [] # close表
|
|
|
endarray = [1, 2, 3, 8, 0, 4, 7, 6, 5]
|
|
|
initobj = Statusobj()
|
|
|
initobj.array = list(map(int, input("请输入原始状态的八数码序列：").split()))
|
|
|
initobj.deep = 0 # 初始化执行深度
|
|
|
initobj.Fn = initobj.deep + countnotinplace(initobj.array, endarray)
|
|
|
openlist.append(initobj)
|
|
|
array_reverse = getreversenum(initobj.array) - initobj.array.index(0)
|
|
|
end_reverse = getreversenum(endarray) - endarray.index(0)
|
|
|
if array_reverse % 2 == end_reverse % 2:
|
|
|
while True:
|
|
|
if openlist[0].array == endarray: # 达到目标状态
|
|
|
end_list = []
|
|
|
end_list.append(openlist[0])
|
|
|
deep = openlist[0].deep
|
|
|
closelist.append(openlist[0])
|
|
|
del openlist[0]
|
|
|
father = closelist[-1].Father
|
|
|
while father.deep >= 1:
|
|
|
end_list.append(father)
|
|
|
father = father.Father
|
|
|
end_list.append(initobj)
|
|
|
print("目标状态：")
|
|
|
printarray(endarray)
|
|
|
print("【变换成功,共需要" + str(deep) + "次变换】")
|
|
|
d = 0
|
|
|
for it in reversed(end_list):
|
|
|
print("当前深度为：{}".format(d))
|
|
|
d += 1
|
|
|
print("操作序号为：{}".format(it.preoperate))
|
|
|
printarray(it.array)
|
|
|
sys.exit()
|
|
|
else:
|
|
|
zero_index = openlist[0].array.index(0)
|
|
|
temp_list = []
|
|
|
operation = selectoperate(zero_index, openlist[0].preoperate)
|
|
|
for ope in operation:
|
|
|
copy_array = openlist[0].array.copy() # .copy()复制序列，必不可少
|
|
|
new_array = newarray(ope, copy_array)
|
|
|
new_obj = Statusobj()
|
|
|
new_obj.array = new_array # 序列
|
|
|
new_obj.deep = openlist[0].deep + 1 # 深度
|
|
|
new_obj.preoperate = ope # 上一操作符
|
|
|
new_obj.Father = openlist[0] # 父亲节点
|
|
|
new_obj.Fn = new_obj.deep + countnotinplace(new_array, endarray) # 评估函数
|
|
|
temp_list.append(new_obj)
|
|
|
closelist.append(openlist[0])
|
|
|
del openlist[0]
|
|
|
for item in temp_list:
|
|
|
openlist.append(item)
|
|
|
openlist.sort(key=lambda x: x.Fn)
|
|
|
else:
|
|
|
print("此情况下无解！")
|
|
|
|
|
|
|
|
|
main()
|
|
|
# 2 8 3 1 6 4 7 0 5 |
