100天每日一题（day12）

题解：

大名鼎鼎的N皇后问题，一直拖着没做，结果在每日一题里发现了。

不会做，看了题解：用到了著名的回溯法（看了别人的解释，回溯就是穷举法剪枝，还是一个深度优先搜索算法）

先安排第一个皇后，再安排第二个皇后。。遇到没位置安排的皇后，就返回上一步，把上一个皇后换个位置

用DFS来做：

class Solution:

    def solveNQueens(self, n: int) -> List[List[str]]:

        ans = list()

        res = [['.']*n for i in range(n)] # 保存最终的结果

        col = [False] *2*n # 指示某一列是否可以放元素

        dg = [False] *2*n # 指示对角线是否合法

        udg = [False] *2*n # 指示反对角线是否合法

 

        def dfs(u):

            list_1 = list()

            # 搜到一个可行答案

            if u == n:

                for i in range(n):

                    list_1.append(''.join(res[i]))

                ans.append(list_1)

                return

            

            # 判断应该在哪一列放皇后

            for i in range(n):

                if not col[i] and not dg[u+i] and not udg[n-u+i]:

                    res[u][i] = 'Q'

                    col[i] = dg[u+i] = udg[n-u+i] = True

                    dfs(u+1)

                    # 恢复现场

                    res[u][i] = '.'

                    col[i] = dg[u+i] = udg[n-u+i] = False

        

        # 从第0行开始搜

        dfs(0)

        return ans