“““
A*搜索解決八數(shù)碼問(wèn)題


“““
#?目標(biāo)狀態(tài)
##GOAL?=?‘‘‘1-2-3
##4-5-6
##7-8-e‘‘‘

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

#?初始狀態(tài)
##INITIAL?=?‘‘‘1-e-2
##6-3-4
##7-5-8‘‘‘

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


#?將狀態(tài)字符串轉(zhuǎn)化為列表
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‘]]
####———————————————————————————

#?將狀態(tài)列表轉(zhuǎn)化為字符串
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的坐標(biāo)
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）
####——————

#?找空格的左、上、右、下四個(gè)位置的元素
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


#?移動(dòng)一個(gè)數(shù)字返回移動(dòng)成功后的狀態(tài)字符串及其父狀態(tài)
def?result（state?action）:
????rows?=?string_to_list（state）
????row_empty?col_empty?=?get_location（rows?‘e‘）??#?獲得當(dāng)前狀態(tài)中