任务描述
本关任务：八数码问题是在一个3×3的棋盘上有1−8位数字随机分布，以及一个空格，与空格相连的棋子可以滑动到空格中，问题的解是通过空格滑动，使得棋盘转化为目标状态，如下图所示。
为了简化问题的输入，首先将空格用数字0表示，然后将3×3的棋盘用9位长的字符串表示，则上图的初始状态为724506831，目标状态为012345678，本关卡所有目标状态均为012345678，也保证初始状态到目标状态有解。
对于上图的初始状态，将数字2移动到空格，称之为u操作（空格上移），将数字3移动到空格，称之为d操作（空格下移），将数字5移动到空格，称之为l操作（空格左移），将数字6移动到空格，称之为r操作（空格右移），则一个合法移动路径为lurdrdllurrdllurrulldrrull。
相关知识
为了完成本关任务，你需要掌握：1.评估函数，2.贪婪最佳优先搜索，3.A*搜索：缩小总评估代价，4.求解思路。
评估函数
在有信息搜索 Informed Search 策略中，常使用的是最佳优先搜索 Best First Search ，它的结点扩展是基于评估函数值f(n)选择的。评估函数被看做是代价估计，因此代价最低的结点最先被选择扩展。
对f(n)的选择决定了搜索策略，大部分的最佳优先搜索算法的f(n)由启发式函数h(n)构成：
h(n)=结点n到目标的最小代价路径的代价估计值
贪婪最佳优先搜索
贪婪最佳优先搜索 Greedy Best-First Search 试图扩展距离目标结点最近的结点，原因是这种策略可能可以非常快的找到解，因此，贪婪最佳优先搜索只使用启发式信息，即f(n)=h(n)。
A*搜索：缩小总评估代价
A* 搜索（A 星搜索）是最广为人知的最佳优先搜索，它对结点n的代价评估结合了g(n)，即到达此结点n已经花费的路径代价，和h(n)，即从该结点n到目标结点所花代价。
f(n)=g(n)+h(n)
由于g(n)是从开始结点到结点n的路径代价，而h(n)是从结点n到目标结点的最小路径代价的估计值因此：
f(n)=经过结点n的最小代价解的估计代价
所以，要寻找最小代价的解，首先扩展的是g(n)+h(n)值最小的结点。可以发现，A* 搜索算法与一致代价搜索算法类似，区别是 A* 搜索算法使用g(n)+h(n)而不是g(n)。
求解思路
该问题是将与空格相连的数字移动到空格的位置上，也就相当于将空格移动到与之相连的位置，因此，以空格为当前结点，扩展结点可能为上下左右四个相连的位置，若使用一般的搜索算法，可能陷入无限搜索中，永远搜不到目标解，而 A* 搜索算法则能非常好的将搜索过程导向求解目标。
问题给的是字符串数据724506831，可以还原成如下形式：
那么空格的l移动操作即为下标4和下标3上所对应的数字的交换，分别为0和5，交换后的新的状态为：
以此类推，空格的lrud各操作均可用以上的交换过程表达。
A* 算法的重中之重就是启发式函数h(n)的设计，不同的设计方法可能产生不同的求解路径。在这里，可以选择欧氏距离作为评估函数值：除0之外，各个数字在当前状态的下标与目标状态的下标的绝对值之和。例如：当前状态为123456780，目标状态为：012345678，数字1的下标分别为0和1，数字2的下标分别为1和2，...，数字8的下标分别为7和8，则当前状态与目标状态的评估值为h(n)=abs(1−2)+abs(2−3)+⋯+abs(7−8)=8。
编程要求
本关的编程任务是补全右侧代码片段 salvePuzzle 、 calcDistH 和 moveMap 中 Begin 至 End 中间的代码，具体要求如下：
-
在 salvePuzzle 中，根据输入参数init（初始状态，如724506831）和targ（目标状态，均为012345678），实现 A* 搜索算法，返回八数码问题的移动路径，如上图的移动路径：lurdrdllurrdllurrulldrrull。
-
在 calcDistH 中，计算当前状态（参数srcmap，如724506831）到目标状态（参数destmap，如012345678）的启发式函数值h(n)，并返回h(n)。
-
在 moveMap 中，实现行动转换，并返回下一个状态，例如当前状态为参数curmap=724506831，当前 8 数码状态curmap中空格 0 的位置索引i=4，移动空格到位置j=3，则返回的新状态为newmap=724056831。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着测试程序会调用上述函数，并判断函数返回的路径是否为合法解，若是则输出 Accepted 表示程序正确，否则程序错误。
以下是平台的测试样例：
测试输入： 724506831
预期输出： Accepted
代码
# -*- coding:utf-8 -*-
class Solution:
def salvePuzzle(self, init, targ):
''' 求解8数码问题
参数：
init - 初始状态 例如'123046758'
targ - 目标状态 均为'012345678'
返回值：
clf - 由udlr组成的移动路径字符串
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
clf = '' # 初始化移动路径字符串
state_open = [] # 初始化开放列表
state_close = [] # 初始化关闭列表
state_open.append([init,99,'test',init,0]) # 将初始状态加入开放列表
fn = 2 # 初始化启发式函数的权重
flag = 1 # 初始化标志位
while True:
cur_state = state_open.pop(0) # 取出开放列表中的第一个状态
state_close.append(cur_state) # 将当前状态加入关闭列表
if cur_state[0] == targ: # 如果当前状态等于目标状态
while 1:
clf += cur_state[2] # 将当前状态的移动方向加入移动路径字符串
if cur_state[3] == init: # 如果当前状态的父状态等于初始状态
break
for id,item in enumerate(state_close[1:]): # 遍历关闭列表中的状态
if item[0] == cur_state[3]: # 如果找到父状态
cur_state = item # 更新当前状态为父状态
return clf[::-1] # 返回逆序的移动路径字符串
i = cur_state[0].find('0') # 找到空格0的位置索引
flag = 1 # 重置标志位
if str(i) not in '036': # 如果空格0不在第一行、第三行和第六行
tmp_map = self.moveMap(cur_state[0],i,i-1) # 尝试将空格0向左移动
if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中
for id,item in enumerate(state_open): # 遍历开放列表中的状态
if item[0] == tmp_map: # 如果找到新状态
if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn: # 如果新状态的代价大于当前状态的代价
state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'l',cur_state[0],cur_state[4]+fn] # 更新开放列表中的状态
flag = 0 # 设置标志位为0
break
break
if flag == 1: # 如果标志位为1
state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'l',cur_state[0],cur_state[4]+fn]) # 将新状态加入开放列表
flag = 1 # 重置标志位
if str(i) not in '258': # 如果空格0不在第二行、第五行和第八行
tmp_map = self.moveMap(cur_state[0],i,i+1) # 尝试将空格0向右移动
if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中
for id,item in enumerate(state_open): # 遍历开放列表中的状态
if item[0] == tmp_map: # 如果找到新状态
if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn: # 如果新状态的代价大于当前状态的代价
state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'r',cur_state[0],cur_state[4]+fn] # 更新开放列表中的状态
flag = 0 # 设置标志位为0
break
break
if flag ==1: # 如果标志位为1
state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'r',cur_state[0],cur_state[4]+fn]) # 将新状态加入开放列表
flag = 1 # 重置标志位
if i-3>=0: # 如果空格0不在最左边的三列
tmp_map = self.moveMap(cur_state[0],i,i-3) # 尝试将空格0向上移动
if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中
for id,item in enumerate(state_open): # 遍历开放列表中的状态
if item[0] == tmp_map: # 如果找到新状态
if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn: # 如果新状态的代价大于当前状态的代价
state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'u',cur_state[0],cur_state[4]+fn] # 更新开放列表中的状态
flag = 0 # 设置标志位为0
break
break
if flag ==1: # 如果标志位为1
state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'u',cur_state[0],cur_state[4]+fn]) # 将新状态加入开放列表
flag = 1 # 重置标志位
if i+3<=8: # 如果空格0不在最右边的三列
tmp_map = self.moveMap(cur_state[0],i,i+3) # 尝试将空格0向下移动
if tmp_map not in [tmp[0] for tmp in state_close]: # 如果新状态不在关闭列表中
for id,item in enumerate(state_open): # 遍历开放列表中的状态
if item[0] == tmp_map: # 如果找到新状态
if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn: # 如果新状态的代价大于当前状态的代价
state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'d',cur_state[0],cur_state[4]+fn] # 更新开放列表中的状态
flag = 0 # 设置标志位为0
break
break
if flag ==1: # 如果标志位为1
state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'d',cur_state[0],cur_state[4]+fn]) # 将新状态加入开放列表
state_open.sort(key=lambda x : x[1] + x[4]) # 根据代价对开放列表进行排序
#********** End **********#
def calcDistH(self, src_map, dest_map):
'''启发式函数h(n)
参数：
src_map - 当前8数码状态
dest_map - 目标8数码状态
返回值：
clf - 当前状态到目标状态的启发式函数值
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if src_map is None or dest_map is None:
return 0
clf = 0
for i in range(9):
clf += abs(int(src_map[i])-int(dest_map[i]))
return clf
#********** End **********#
def moveMap(self, cur_map, i, j):
'''状态转换（交换位置i和j）
参数：
cur_map - 当前8数码状态
i - 当前8数码状态中空格0的位置索引
j - 将空格0的位置i移动到位置j，位置j移动到位置i
返回值：
clf - 新的8数码状态
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if i>j:
i,j=j,i
tmp_i = cur_map[i]
tmp_j = cur_map[j]
tmp_map = cur_map[:i]+tmp_j+cur_map[i+1:j]+tmp_i+cur_map[j+1:]
return tmp_map
#********** End **********#
