A*算法解决八数码问题

“““
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 < 2:  # 可右移
        actions.append（rows[row_empty][col_empty + 1]）
    if row_empty < 2:  # 可下称
        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‘）  # 获得当前状态中