头歌——人工智能（搜索策略）

第1关：搜索策略

什么是搜索技术
人类的思维过程可以看作是一个搜索过程。从小学到现在，你一定遇到过很多智力游戏问题，如传教士和野人问题：有 3 个传教士和 3 个野人来到河边准备过河，河边有一条船，每次最多坐 2 人。但是任何时刻在河的两边以及船上的野人数量不能超过传教士的数量，不然传教士就会被吃掉。

如果让你来玩这个智力游戏，在每一次过河之后都会有几种过河方案供你选择，到底哪种方案才有利于在满足题目所规定的约束条件下顺利过河？这就是搜索问题。

经过反复努力和试探，你终于找到了一种解决办法。在高兴之余，你可能马上又会想到这个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优方案？在计算机上又如何实现这样的搜索？这些问题就是本关要介绍的搜索问题，而求解这类搜索问题的技术称之为搜索技术。

第2关：盲目搜索

编程要求
根据提示，在右侧编辑器补充代码，完成 PlayMazz 函数，实现在迷宫里从起点走到出口的功能。其中：

mazz ：表示迷宫，类型为字典；
start ：表示起点，类型为字符；
end ：表示出口，类型为字符。

测试说明
您只需完成 PlayMazz 函数中的 Begin-End 段即可，平台会对你编写的代码进行测试。其中测试输入为字典的形式，其中 mazz 部分表示迷宫，start 部分表示迷宫起点，end 部分表示迷宫出口。

测试输入：{mazz:{A: [B, C],B: [D, E],C: [F],F: [G, H],D: [],E: [],G: [],H: []},start:A,end:D}

预期输出：ABCD

开始你的任务吧，祝你成功！

def PlayMazz(mazz, start, end):'''走迷宫，从start走到end:param mazz: 迷宫:param start: 迷宫的起点:param end: 迷宫的出口:vertex: 迷宫中正在进行广度优先搜索算法的当前位置'''# queue为队列，当队列为空或者当前地点为H时搜索结束visited, queue = set(), [start]while queue:# 从队列中出队，即当前所处的地点vertex = queue.pop(0)if vertex not in visited:visited.add(vertex)print(vertex, end='')#********* Begin *********## 当走到出口时结束算法if vertex == end:break#********* End *********##********* Begin *********## 将当前所处地点所能走到的地点放入队列for v in mazz[vertex]:if v not in visited:queue.append(v)#********* End *********#

第3关：启发式搜索 - 扫地机器人最短路径搜索

编程要求
在右侧编辑器补充代码，完成 A_star 函数，实现从 start 走到 end 的自动寻路功能。其中：

map ：表示地图。
start ：表示出发地，类型为列表，如 [1,2] 表示出发地为地图中的第 1 行第 2 列的方块。
end ：表示目的地，类型为列表，如 [1,2] 表示目的地为地图中的第 1 行第 2 列的方块。

测试说明
您只需完成 A_star 函数中的 Begin-End 段即可，平台会对你编写的代码进行测试，并将您寻找到的路径打印出来。其中测试输入为字典的形式，其中 map_size 部分表示地图的长和宽， start 部分表示出发地的坐标， end 部分表示目的地的坐标， obstacleList 部分表示障碍物坐标的列表。

测试输入：
{‘map_size’:[10, 10], ‘start’:[1, 2], ‘end’:[6, 7], ‘obstacleList’:[[1, 1], [2, 1], [3, 1], [4, 3], [1, 3], [2, 3], [3, 3], [0, 1], [5, 1], [5, 3]]}

预期输出：
start->(1,4)->(2,5)->(3,6)->(4,7)->(5,8)->(6,8)->end

开始你的任务吧，祝你成功！

from a_star_utils import Nodedef A_star(map, mapSize, start, end):'''A*算法，从start走到end:param map:地图:param mapSize:地图大小，例如[10,10]表示地图长10宽10:param start:表示出发地，类型为列表，如[1,2]表示出发地为地图中的第1行第2列的方块:param end:表示目的地，类型为列表，如[1,2]表示目的地为地图中的第1行第2列的方块:return:从出发地到目的地的路径'''openedList = []closedList = []#********* Begin *********## 获得出发地方块的信息，并将信息保存为 node 变量startNode = map[start[0]][start[1]]startNode.distanceFromOri = 0startNode.allDistance = startNode.distanceFromOri + startNode.distanceFromDesstartNode.parent = Nonenode = startNode  # 将当前方块保存为 node 变量#********* End *********##********* Begin *********## 将当前方块存到开启列表中openedList.append(node)node.added = True#********* End *********#while len(openedList) != 0:# 从开启列表中取出F值最小的节点node = openedList.pop(0)node.closed = True# 如果当前节点是终点，结束搜索并回溯路径if node.y == end[0] and node.x == end[1]:finalPath = []while node is not None:finalPath.append(node)node = node.parentfinalPath.reverse()return finalPath# 开始检查邻居节点neighboursList = []y, x = node.y, node.xparentDistanceFromOri = node.distanceFromOri# 寻找周围的邻居节点（上下左右斜向）for dy in (y + 1, y, y - 1):if dy < 0 or dy >= mapSize[0]:continuefor dx in (x + 1, x, x - 1):if dx < 0 or dx >= mapSize[1]:continueneedNode = map[dy][dx]# 跳过障碍物或已处理过的节点if needNode.unable or needNode.closed or needNode.added:continue# 计算距离代价if abs(dy - y) + abs(dx - x) == 1:  # 直线代价distanceFromOri = parentDistanceFromOri + 1else:  # 对角线代价distanceFromOri = parentDistanceFromOri + 1.4# 更新邻居节点的G值（距离起点的代价）if needNode in neighboursList:if distanceFromOri < needNode.distanceFromOri:needNode.distanceFromOri = distanceFromOrielse:needNode.distanceFromOri = distanceFromOrineighboursList.append(needNode)# 处理每个邻居节点，计算F值并加入开启列表for needNode in neighboursList:needNode.parent = node# 计算F值needNode.allDistance = needNode.distanceFromOri + needNode.distanceFromDesneedNode.added = TrueopenedList.append(needNode)# 将开启列表按照F值进行排序，F值小的优先处理openedList.sort(key=lambda x: x.allDistance)return None

第4关：搜索算法应用 - 四皇后问题

任务描述
本关任务：编写一个能求解四皇后问题的 Python 程序。

相关知识
为了完成本关任务，你需要掌握四皇后问题。

四皇后问题
在 n 行 n 列的国际象棋上摆放 n 个皇后，使其不能互相攻击（即任意两个皇后都不能处于同一行、同一列或同一斜线上）。请问有多少种摆法，以及如何摆放这些皇后。这就是经典的 n 皇后问题。如下图所示：

编程要求
根据提示，在右侧编辑器补充代码，完成 FourQueens 函数，实现找出所有可能的皇后摆法。其中：

mark ：表示皇后的位置信息，例如 [0,1,3,2] 表示棋盘的第 1 行第 1 列，第 2 行第 2 列，第 3 行第 4 列，第 4 行第 3 列放置了皇后。例如 [1, None, None, None] 表示第 1 行第 2 列放置了皇后，其他行没有放置皇后。

cur ：表示当前准备在第几行放置皇后，例如 cur=1 时，表示准备在第 2 行放置皇后。

result :表示存放皇后摆放结果的列表，类型为二维 list。

测试说明
您只需完成 FourQueens 函数中的 Begin-End 段即可，平台会对你编写的代码进行测试，并将所有皇后的摆放方式打印出来。

预期输出：

---

XQXX
XXXQ
QXXX
XXQX

---

XXQX
QXXX
XXXQ
XQXX

---

开始你的任务吧，祝你成功！

def make(mark):'''标记皇后的位置，例如mark[0] = 2, 表示第1行皇后放在第3列的位置:param mark: 皇后的位置信息:return: 拼接好的结果'''#初始化数组r = [['X' for _ in range(len(mark))] for _ in range(len(mark))]#将每一行中皇后的位置用‘Q’代替for i in range(len(mark)):r[i][mark[i]] = 'Q'#枚举，将原来散的元素连接成字符串for k, v in enumerate(r):r[k] = ''.join(v)return rdef FourQueens(mark, cur, ret):'''深度优先搜索的方式求解四皇后问题:param mark:表示皇后的位置信息，例如[0,1,3,2]表示棋盘的第1行第1列，第2行第2列，第3行第4列，第4行第3列放置了皇后。例如[1, None, None, None]表示第1行第2列放置了皇后，其他行没有放置皇后。初始值为[None,None,None,None]:param cur:表示当前准备在第几行放置皇后，例如`cur=1`时，表示准备在第`2`行放置皇后。初始值为0:param ret:表示存放皇后摆放结果的列表，类型为列表。初始值为[]:return:无'''if cur == len(mark):#********* Begin *********## 如果当前行是最后一行，记录一个解，并返回结束此次搜索ret.append(make(mark))return#********* End *********##试探处理，将当前行的皇后应该在的位置遍历每一列，如果满足条件，递归调用处理下一行for i in range(len(mark)):mark[cur], down = i, Truefor j in range(cur):# 当想在当前位置放皇后会与其他皇后冲突时不放置皇后if mark[j] == i or abs(i-mark[j]) == cur - j:down = Falsebreakif down:# 准备在下一行找能放置皇后的位置FourQueens(mark, cur+1, ret)