宽度优先算法

“““
宽度优先搜索解决八数码问题

上机要求：
（1）在此代码基础上完成深度优先搜索和A*搜索，并显示结果。当场验收。
（2）完成上机报告

“““


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


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:  # 可下称