八數碼問題 (頭歌 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:
將兩個寫在一起，但是代碼有點冗長