class Solution:

    def totalNQueens(self, n: int) -> int:

        def backtrack(i,tmp,col,z_diagonal,i_diagonal):

            if i == n:

                nonlocal res

                res += 1

                return

            for j in range(n):

                if j not in col and i+j not in z_diagonal and i-j not in i_diagonal:

                    backtrack(i+1,tmp+[s[:j]+"Q"+s[j+1:]],col|{j},z_diagonal|{i+j},i_diagonal|{i-j})

        s = "." * n

        res = 0

        backtrack(0,[],set(),set(),set())

        return res

class Solution:

    def totalNQueens(self, n: int) -> int:

        def backtrack(row = 0, hills = 0, next_row = 0, dales = 0, count = 0):

            """

            :type row: 当前放置皇后的行号

            :type hills: 主对角线占据情况 [1 = 被占据，0 = 未被占据]

            :type next_row: 下一行被占据的情况 [1 = 被占据，0 = 未被占据]

            :type dales: 次对角线占据情况 [1 = 被占据，0 = 未被占据]

            :rtype: 所有可行解的个数

            """

            if row == n:  # 如果已经放置了 n 个皇后

                count += 1  # 累加可行解

            else:

                # 当前行可用的列

                # ! 表示 0 和 1 的含义对于变量 hills, next_row and dales的含义是相反的

                # [1 = 未被占据，0 = 被占据]

                free_columns = columns & ~(hills | next_row | dales)

                # 找到可以放置下一个皇后的列

                while free_columns:

                    # free_columns 的第一个为 '1' 的位

                    # 在该列我们放置当前皇后

                    curr_column = - free_columns & free_columns

                    # 放置皇后

                    # 并且排除对应的列

                    free_columns ^= curr_column

                    count = backtrack(row + 1,

                                      (hills | curr_column) << 1,

                                      next_row | curr_column,

                                      (dales | curr_column) >> 1,

                                      count)

            return count

        # 棋盘所有的列都可放置，

        # 即，按位表示为 n 个 '1'

        # bin(cols) = 0b1111 (n = 4), bin(cols) = 0b111 (n = 3)

        # [1 = 可放置]

        columns = (1 << n) - 1

        return backtrack()

class Solution:

    def totalNQueens(self, n: int) -> int:

        def DFS(n: int, row: int, cols: int, left: int, right: int):

            """ 深度优先搜索

            :param n: N皇后个数

            :param row: 递归的深度

            :param cols: 可被攻击的列

            :param left: 左侧斜线上可被攻击的列

            :param right: 右侧斜线上可被攻击的列

            """

            if row >= n:

                self.res += 1

                return

            # 获取当前可用的空间

            bits = (~(cols | left | right)) & ((1 << n) - 1)

            # 遍历可用空间

            while bits:

                # 获取一个位置

                p = bits & -bits

                DFS(n, row + 1, cols | p, (left | p) << 1, (right | p) >> 1)

                bits = bits & (bits - 1)

        if not (n == 1 or n >= 4):

            # N皇后问题只有在 N 大于等于 4 或等于 1 的时候才有解

            return 0

        self.res = 0

        DFS(n, 0, 0, 0, 0)

        return self.res