八数码问题(头歌educoder启发式搜索)(python实现)

任务描述
本关任务：八数码问题是在一个3×3的棋盘上有1−8位数字随机分布，以及一个空格，与空格相连的棋子可以滑动到空格中，问题的解是通过空格滑动，使得棋盘转化为目标状态，如下图所示。为了简化问题的输入，首先将空格用数字0表示，然后将3×3的棋盘用9位长的字符串表示，则上图的初始状态为724506831，目标状态为012345678，本关卡所有目标状态均为012345678，也保证初始状态到目标状态有解。

测试输入：
724506831 

这道题可以用很多搜索方法解决，启发式搜索为题目要求方法，但是因为评测的程序是只要有一条路径能够成功从输入走到"12345678"即可，于是也可以使用其他搜索方法也可以,比如深搜，广搜都可以，甚至不需要计算代价函数，无脑搜索就可以，但是后来发现不用代价值判断会超时，所以还是加入了代价函数的编写,由于不能贴完整代码，给大家一个模板，大家去写子函数把

深度优先搜索搜模板

子函数:
self.path1(index, i)  index位置是否能够移动
self.moveMap1(init, index, index + self.direction[i]) #index位置与index +direction[i] 交换后的序列
self.isseen(change) change序列是否被走过
self.calcDistH(change) 计算change到targ的代价值




class Solution:
    def __init__(self):
        self.set1 = set()
        self.seen = collections.defaultdict(int) #标记数组
        self.way= {0:'r',1:'l',2:'d',3:'u'}  #存储走的方向
        self.path =[]  #存储路径
        self.direction = (1, -1, 3, -3) #存储移动

    def salvePuzzle(self, init, targ):
        ''' 求解8数码问题
        参数：
        init - 初始状态 例如'123046758'
        targ - 目标状态 均为'012345678'
        返回值：
        clf - 由udlr组成的移动路径字符串
        '''
        return self.dfs(init, targ)

    def dfs(self, init, targ):
        initstr = ''.join(init)
        if (initstr == targ):  # 如果找到就返回
            return True
        self.seen[initstr] = 1  # 标记为走过
        nowvalue = self.calcDistH(init, targ)  # 计算当前的代价值
        index = init.index('0')  # 找到0的位置
        for i in range(4):  #遍历四种方向
            if (self.path1(index, i)):  # 如果能够交换
                change = self.moveMap1(init, index, index + self.direction[i])  #得到移动后的序列
                changevalue = self.calcDistH(change, targ)  #移动后的序列代价值
                if (changevalue<=nowvalue and self.isseen(change)):  #判断change是否走过
                    self.path.append(self.way[i])  #
                    if(self.dfs(change, targ)):
                        return self.path
                    self.path.pop()  #回溯
        return 0  
    
a=Solution()
str1 = input()
print(a.salvePuzzle(list(str1),"012345678")) #打印路径

广度优先搜索模板
明天写明天写

class Solution:
    def __init__(self):
        self.set1 = set()
        self.seen = collections.defaultdict(int)  # 标记数组
        self.way = {0: 'r', 1: 'l', 2: 'd', 3: 'u'}  # 存储走的方向
        self.direction = (1, -1, 3, -3)  # 存储移动
        self.queue = collections.deque()


    def salvePuzzle(self, init, targ):
        ''' 求解8数码问题
        参数：
        init - 初始状态 例如'123046758'
        targ - 目标状态 均为'012345678'
        返回值：
        clf - 由udlr组成的移动路径字符串
        '''
        self.queue.append((init, list())) #两个参数，一个初始序列与经过路径
        return self.bfs(targ)

    def bfs(self,targ):
        while self.queue:
            (init,path) = self.queue.popleft()
            initstr = ''.join(init)
            self.set1.add(initstr)  #标记为走过724506831
            if (initstr == targ):  #如果找到就返回
                return path
            nowvalue = self.calcDistH(init, targ)  # 计算当前的代价值
            index = init.index('0')  # 找到0的位置
            for i in range(4):  # 遍历四种方向
                if (self.path1(index, i)):  # 如果满足条件才进行下去):  # 如果能够交换
                    change = self.moveMap1(init, index,index + self.direction[i])  # 得到移动后的序列
                    changevalue = self.calcDistH(change, targ)  # 移动后的序列代价值
                    if (changevalue <= nowvalue and ''.join(change) not in self.set1):  # 判断change是否走过且代价值更小
                        temp = deepcopy(path)  #深拷贝防止在原数组上更改
                        temp.append(self.way[i])
                        self.queue.append((change,temp)) #加入队列
        return 0

截图

可以使用集合来纪录走过的路径,与这道题测试和题目是一样的，宽搜可以找到最优的，但是运行时间有点长，但

bfs+dfs:
将两个写在一起，但是代码有点冗长