实验一：盲目搜索算法

第1关：广度优先搜索

编程要求

根据提示补全右侧编辑器 Begin-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: 图的出口
    '''
    # queue为队列，当队列为空或者当前地点为终点时搜索结束
    visited, queue = set(), [start]
    ans = []
    #********* Begin *********#
    while queue:
        node = queue.pop(0)
        ans.append(node)
        if node==end:
            break
        for c in mazz[node]:
            queue.append(c)
    print(''.join(ans))
    #********* End *********#

第2关：深度优先搜索

编程要求

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

测试说明

平台会对你编写的代码进行测试：
测试输入：
{‘graph’:{‘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:
    #     return
    #********* Begin *********#
    # 看看当前位置有哪些路可以走，如果能走并且之前没有走过就走
    stack = [start]
    ans = []
    while stack:
        node = stack.pop(-1)
        if node in visited:
            continue
        ans.append(node)
        visited.add(node)
        if node==end:
            break
        for c in graph[node][::-1]:
            stack.append(c)
    print(''.join(ans))
    #********* End *********#

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

编程要求

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

• 在 solveNQueens 中，利用 DFS 函数实现N皇后问题求解，并返回方案总数；
• 在 DFS 中，利用深度优先搜索算法的思想，递归求解N皇后问题。

  测试说明

  平台会对你编写的代码进行测试：
  测试输入：1
  预期输出：1
  输入格式：整数，表示皇后数量。
  输出格式：整数，表示 N 皇后放置方案总数。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self, n=0):
        # self.vis = [[0]*n for _ in range(n)]    #用于标记是否存在皇后的二维列表（初始值全为0）
        self.ans = 0                #用于存储答案（N皇后方案数，初始值0）
        self.n = n                  #用于存储皇后数量n
    def solveNQueens(self):
        """求解N皇后问题（调用self.DFS函数）
        :rtype: self.ans: int    #返回N皇后放置方案数
        """
        #请在这里补充代码，完成本关任务
        #********** Begin ********#
        self.exit_column = set()
        self.exit_diagonal1 = set()
        self.exit_diagonal2 = set()
        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 += 1
            return
        for i in range(n):
            if i not in self.exit_column and i+row not in self.exit_diagonal1 and i-row not in self.exit_diagonal2:
                self.exit_column.add(i)
                self.exit_diagonal1.add(i+row)
                self.exit_diagonal2.add(i-row)
                self.DFS(row+1, n)
                self.exit_column.remove(i)
                self.exit_diagonal1.remove(i+row)
                self.exit_diagonal2.remove(i-row)
        #********** End **********#