import copy
# 棋盤的類，實現(xiàn)移動和擴展狀態(tài)
class grid:
    def __init__(self, stat):
        self.pre = None
        self.target = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
        self.stat = stat
        self.find0()
        self.update()
    #更新深度和距離和
    def update(self):
        self.fH()
        self.fG()
 
    # G是深度，也就是走的步數(shù)
    def fG(self):
        if (self.pre != None):
            self.G = self.pre.G + 1
        else:
            self.G = 0
 
    # H是和目標狀態(tài)距離之和，可以用來判斷是否找到解
    def fH(self):
 
        self.H = 0
        for i in range(3):
            for j in range(3):
                targetX = self.target[i][j]
                nowP = self.findx(targetX)
                self.H += abs(nowP[0] - i) + abs(nowP[1] - j)
 
    #以三行三列的形式輸出當前狀態(tài)
    def see(self):
        print("depth:", self.G)
        for i in range(3):
            print(self.stat[i])
        print("-" * 10)
 
    # 查看找到的解是如何從頭移動的
    def seeAns(self):
        ans = []
        ans.append(self)
        p = self.pre
        while (p):
            ans.append(p)
            p = p.pre
        ans.reverse()
        for i in ans:
            i.see()
    #找到數(shù)字x的位置
    def findx(self, x):
        for i in range(3):
            if (x in self.stat[i]):
                j = self.stat[i].index(x)
                return [i, j]
    #找到0的位置，也就是空白格的位置
    def find0(self):
        self.zero = self.findx(0)
 
    #對當前狀態(tài)進行擴展，也就是上下左右移動，返回的列表中是狀態(tài)的二維列表，不是對象
    def expand(self):
        i = self.zero[0]
        j = self.zero[1]
        gridList = []
        if (j == 2 or j == 1):
            gridList.append(self.left())
        if (i == 2 or i == 1):
            gridList.append(self.up())
        if (i == 0 or i == 1):
            gridList.append(self.down())
        if (j == 0 or j == 1):
            gridList.append(self.right())
        return gridList
 
    # deepcopy多維列表的復制，防止指針賦值將原列表改變
    # move只能移動行或列，即row和col必有一個為0
    #對當前狀態(tài)進行移動的函數(shù)
    def move(self, row, col):
        newStat = copy.deepcopy(self.stat)
        tmp = self.stat[self.zero[0] + row][self.zero[1] + col]
        newStat[self.zero[0]][self.zero[1]] = tmp
        newStat[self.zero[0] + row][self.zero[1] + col] = 0
        return newStat
 
    def up(self):
        return self.move(-1, 0)
 
    def down(self):
        return self.move(1, 0)
 
    def left(self):
        return self.move(0, -1)
 
    def right(self):
        return self.move(0, 1)
 
# 判斷狀態(tài)g是否在狀態(tài)集合中，g是對象，gList是對象列表
# 返回的結(jié)果是一個列表，第一個值是真假，如果是真則第二個值是g在gList中的位置索引
def isin(g, gList):
    gstat = g.stat
    statList = []
    for i in gList:
        statList.append(i.stat)
    if (gstat in statList):
        res = [True, statList.index(gstat)]
    else:
        res = [False, 0]
    return res
 
# 計算逆序數(shù)之和
def N(nums):
    N=0
    for i in range(len(nums)):
        if(nums[i]!=0):
            for j in range(i):
                if(nums[j]>nums[i]):
                    N+=1
    return N
 
# 根據(jù)逆序數(shù)之和判斷所給八數(shù)碼是否可解
def judge(src,target):
    N1=N(src)
    N2=N(target)
    if(N1%2==N2%2):
        return True
    else:
        return False
 
# 初始狀態(tài)
startStat = [[2, 8, 3], [1, 0, 4], [7, 6, 5]]
g = grid(startStat)
# 判斷所給的八數(shù)碼受否有解
if(judge(startStat,g.target)!=True):
    print("所給八數(shù)碼無解，請檢查輸入")
    exit(1)
# visited儲存的是已經(jīng)擴展過的節(jié)點
visited = []
time = 0
# 用遞歸的方式進行DFS遍歷
def DFSUtil(v, visited):
    global time
    #判斷是否達到深度界限
    if (v.G > 4):
        return
    time+=1
    #判斷是否已經(jīng)找到解
    if (v.H == 0):
        print("found and times", time, "moves:", v.G)
        v.seeAns()
        exit(1)
 
    #對當前節(jié)點進行擴展
    visited.append(v.stat)
    expandStats = v.expand()
    w = []
    for stat in expandStats:
        tmpG = grid(stat)
        tmpG.pre = v
        tmpG.update()
        if (stat not in visited):
            w.append(tmpG)
    for vadj in w:
        DFSUtil(vadj, visited)
    #visited查重只對一條路，不是全局的，每條路開始時都為空
    #因為如果全局查重，會導致例如某條路在第100層找到的狀態(tài)，在另一條路是第2層找到也會被當做重復
    #進而導致明明可能會找到解的路被放棄
    visited.pop()
 
DFSUtil(g, visited)
# 如果找到解程序會在中途退出，走到下面這一步證明沒有找到解
print("在當前深度下沒有找到解，請嘗試增加搜索深度")