题解 | #N皇后问题#

回溯法，采用递归的方式，当路径达到临界值时退出,当前路径符合条件时将其路径并在递归结束时退出该路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 the n
# @return int整型
#
class Solution:
    def Nqueen(self , n: int) -> int:
        # write code here
        matrix = [["." for _ in range(n)] for _ in range(n)]
        res = 0
        def check(r, c, matrix):
            for i in range(r):
                if matrix[i][c] == "Q":
                    return False
            i, j = r, c
            while i > 0 and j > 0:
                if matrix[i - 1][j - 1] == "Q":
                    return False
                i -= 1
                j -= 1
            i, j = r, c
            while i > 0 and j < n - 1:
                if matrix[i - 1][j + 1] == "Q":
                    return False
                i -= 1
                j += 1
            return True
        def dfs(r):
            nonlocal res, matrix
            if r == n:
                res += 1
                return
            for i in range(n):
                if check(r, i, matrix):
                    matrix[r][i] = "Q"
                    dfs(r + 1)
                    matrix[r][i] = "."
        dfs(0)
        return res