#?計算狀態對應的逆序數
def?THEnum（node）:
????Sum?=?0
????for?i?in?range（1?9）:
????????num?=?0
????????for?j?in?range（0?i）:
????????????if?node[j]?>?node[i]?and?node[i]?!=?‘0‘:
????????????????num?=?num?+?1
????????Sum?+=?num
????return?Sum


#?h（n）函數，用于計算估價函數f（n），這里的h（n）選擇的是與目標相比錯位的數目
def?Hn（node）:
????global?goal
????hn?=?0
????for?i?in?range（0?9）:
????????if?node[i]?!=?goal[i]:
????????????hn?+=?1
????return?hn


#?拓展node狀態對應的子結點
def?Expand（node）:
????global?expand
????tnode?=?[]
????state?=?node.index（“0“）
????elist?=?expand[state]
????j?=?state
????for?i?in?elist:
????????j?=?state
????????if?i?>?j:
????????????i?j?=?j?i
????????re?=?node[:i]?+?node[j]?+?node[i?+?1:j]?+?node[i]?+?node[j?+?1:]
????????tnode.append（re）
????return?tnode


#?將最后的結果按格式輸出
def?PRINT（result）:
????for?i?in?range（len（result））:
????????print（“step--“?+?str（i?+?1）+“|“）
????????print（“|“+result[i][:3]+“|“）
????????print（“|“+result[i][3:6]+“|“）
????????print（“|“+result[i][6:]+“|“）


#?選擇opened表中的最小的估價函數值對應的狀態
def?MIN（opened）:
????ll?=?{}
????for?node?in?opened:
????????k?=?Fn[node]
????????ll[node]?=?k
????kk?=?min（ll?key=ll.get）
????return?kk


#?主程序開始
opened?=?[]
closed?=?[]
Gn?=?{}??#?用來存儲狀態和對應的深度，也就是初始結點到當前結點的路徑長度
Fn?=?{}??#?用來存放狀態對應的估價函數值
parent?=?{}??#?用來存儲狀態對應的父結點

#?expand中存儲的是九宮格中每個位置對應的可以移動的情況
#?當定位了0的位置就可以得知可以移動的情況
expand?=?{0:?[1?3]?1:?[0?2?4]?2:?[1?5]
??????????3:?[0?4?6]?4:?[3?1?5?7]?5:?[4?2?8]
??????????6:?[3?7]?7:?[6?4?8]?8:?[7?5]}


print（“若輸入‘123405678’代表8數碼的狀態為：“）
print（“|123|“）
print（“|405|“）
print（“|678|“）
start?=?input（“請輸入初始狀態：