头歌——人工智能（盲目搜索算法）

第1关：广度优先搜索

任务描述
本关任务：编写代码实现广度优先搜索一个给定的树。

相关知识
为了完成本关任务，你需要掌握广度优先搜索算法的原理与实现。

代码

def PlayMazz(mazz, start, end):'''走迷宫，从start走到end:param mazz: 图:param start: 图的起点:param end: 图的出口'''# queue为队列，当队列为空或者当前地点为终点时搜索结束queue =list()closed=set()queue.append(start)#********* Begin *********#while(queue!=0):closed.add(queue[0])if queue[0]==end:print(end,end='')breakelse:print(queue[0],end='')for i in mazz[queue[0]]:if i in closed:passelse:queue.append( i )queue.remove(queue[0])#********* End *********#

第2关：深度优先搜索

编程要求
根据提示，补全右侧编辑器中 Begin-End 区间中 PlayMazz 函数中的代码，来实现对整棵树的深度优先搜索。

测试说明
平台会对你编写的代码进行测试：

测试输入：

{‘mazz’:{‘A’:[‘B’,‘E’],‘B’:[‘C’,‘D’],‘C’:[],‘D’:[],‘E’:[]},‘start’:‘A’,‘end’:‘E’}
预期输出：

ABCDE

代码

def PlayMazz(graph, start,end, visited=None):'''深度优先搜索，从1走到9:param graph: 搜索的空间:param start: 开始搜索的起点:param visited:  已经搜索过的点集合'''if visited is None:visited = set()visited.add(start)print(start, end='')# 当前地点为终点时结束搜索if start == end:returnelse:for i in graph[start]:PlayMazz(graph,i,end)#********* Begin *********## 看看当前位置有哪些路可以走，如果能走并且之前没有走过就走#********* End *********#

第3关：盲目搜索算法的应用

编程要求
本关的编程任务是，补全右侧编辑 Begin-End 区间的代码，使函数 solveNQueens 和函数 DFS 实现指定功能 ，具体要求如下：

在 solveNQueens 中，利用 DFS 函数实现N皇后问题求解，并返回方案总数；

在 DFS 中，利用深度优先搜索算法的思想，递归求解N皇后问题。

测试说明
平台会对你编写的代码进行测试：

测试输入：1

预期输出：1

输入格式：整数，表示皇后数量。

输出格式：整数，表示 N 皇后放置方案总数。

代码

class Solution:def __init__(self, n=0):self.vis = [0]*n  # 用于标记是否存在皇后的二维列表（初始值全为0）self.ans = 0  # 用于存储答案（N皇后方案数，初始值0）self.n = n  # 用于存储皇后数量ndef solveNQueens(self):"""求解N皇后问题（调用self.DFS函数）:rtype: self.ans: int    #返回N皇后放置方案数"""# 请在这里补充代码，完成本关任务# ********** Begin **********#self.DFS(0,self.n)return self.ans# ********** End **********#def DFS(self, row, n):"""深度优先搜索N皇后问题的解空间:type: row: int      #NxN棋盘的第row行:type: n: int        #皇后数量n:rtype: None         #无返回值"""# 请在这里补充代码，完成本关任务# ********** Begin **********#if row == n:self.ans += 1returnwhile self.vis[row] < n:# print(1)if self.judge(row):self.DFS(row + 1, self.n)self.vis[row] += 1else:self.vis[row] += 1if self.vis[row] == n:self.vis[row] = 0return# ********** End **********#def judge(self,row):  # 判断是否在同一列、同一对角线上if row == 0:return Truefor i in range(row):if abs(self.vis[row] - self.vis[i]) == row - i or self.vis[row] == self.vis[i]:  # 若在对角线上则两个皇后横轴和纵轴的距离相等return Falsereturn True