题解 | N皇后问题

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 the n
# @return int整型
#
class Solution:
    def Nqueen(self , n: int) -> int:
        # write code here
        result = []


        def dfs(row, used_cols, used_dig1, used_dig2, path):

            # 递归终止条件
            if len(path) == n:
                result.append(path.copy())
                return

            # 逐列遍历
            for col in range(n):

                # 剪枝
                dig1 = row - col
                dig2 = row + col
                if col in used_cols or dig1 in used_dig1 or dig2 in used_dig2:
                    continue

                # 处理当前节点
                used_cols.add(col)
                used_dig1.add(dig1)
                used_dig2.add(dig2)
                path.append('·'* col + 'Q' + '·'* (n-col-1))

                # 递归
                dfs(row+1,used_cols, used_dig1, used_dig2, path)

                # 回溯
                used_cols.remove(col)
                used_dig1.remove(dig1)
                used_dig2.remove(dig2)
                path.pop()

        dfs(0, set(), set(), set(),[])
        return len(result)