“““
A*搜索解決八數碼問題


“““
#?目標狀態
##GOAL?=?‘‘‘1-2-3
##4-5-6
##7-8-e‘‘‘

GOAL?=?‘‘‘1-2-3
8-e-4
7-6-5‘‘‘

#?初始狀態
##INITIAL?=?‘‘‘1-e-2
##6-3-4
##7-5-8‘‘‘

INITIAL?=?‘‘‘1-e-3
7-2-4
6-8-5‘‘‘


#?將狀態字符串轉化為列表
def?string_to_list（input_string）:
????return?[x.split（‘-‘）?for?x?in?input_string.split（‘\n‘）]


##print（string_to_list（INITIAL））
####———————————————————————————
####?[[‘1‘?‘e‘?‘2‘]?[‘6‘?‘3‘?‘4‘]?[‘7‘?‘5‘?‘8‘]]
####———————————————————————————

#?將狀態列表轉化為字符串
def?list_to_string（input_list）:
????return?‘\n‘.join（[‘-‘.join（x）?for?x?in?input_list]）


##print（list_to_string（[[‘1‘?‘e‘?‘2‘]?[‘6‘?‘3‘?‘4‘]?[‘7‘?‘5‘?‘8‘]]））
####——————
####?1-e-2
####?6-3-4
####?7-5-8
####——————

#?獲取e的坐標
def?get_location（rows?input_element）:
????for?i?row?in?enumerate（rows）:
????????for?j?item?in?enumerate（row）:
????????????if?item?==?input_element:
????????????????return?i?j


##print（get_location（[[‘1‘?‘e‘?‘2‘]?[‘6‘?‘3‘?‘4‘]?[‘7‘?‘5‘?‘8‘]]‘e‘））
####——————
####?（0?1）
####——————

#?找空格的左、上、右、下四個位置的元素
def?actions（cur_state）:
????rows?=?string_to_list（cur_state）
????row_empty?col_empty?=?get_location（rows?‘e‘）
????actions?=?[]
????if?col_empty?>?0:??#?可左移
????????actions.append（rows[row_empty][col_empty?-?1]）
????if?row_empty?>?0:??#?可上移
????????actions.append（rows[row_empty?-?1][col_empty]）
????if?col_empty?????????actions.append（rows[row_empty][col_empty?+?1]）
????if?row_empty?????????actions.append（rows[row_empty?+?1][col_empty]）
????return?actions


#?移動一個數字返回移動成功后的狀態字符串及其父狀態
def?result（state?action）:
????rows?=?string_to_list（state）
????row_empty?col_empty?=?get_location（rows?‘e‘）??#?獲得當前狀態中