52.md

题目地址

https://leetcode-cn.com/problems/n-queens-ii/

解答1

class Solution:
    def totalNQueens(self, n: int) -> int:
        """
            N皇后II(非最优解)

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            输入: 4
            输出: 2
            解释: 4 皇后问题存在如下两个不同的解法。
            [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
        """
        board = ['.'] * (n ** 2)

        res = []

        col_flag = [1] * n
        major_diag_flag = [1] * (2 * n - 1)
        minor_diag_flag = [1] * (2 * n - 1)

        self.solve_queen(board, 0, res, n, col_flag, major_diag_flag, minor_diag_flag)

        return len(res)

    def solve_queen(self, board, row, res, n, col_flag, major_diag_flag, minor_diag_flag):

        if row == n:
            new_board = list(board)
            res.append(new_board)
        else:
            for col in range(n):
                # 对于从左到右的对角线row-col为常数，从右到左的对角线row+col为常数
                if col_flag[col] and major_diag_flag[row - col] and minor_diag_flag[row + col]:
                    board[row * n + col] = 'Q'
                    col_flag[col] = 0
                    major_diag_flag[row - col] = 0
                    minor_diag_flag[row + col] = 0

                    self.solve_queen(board, row + 1, res, n, col_flag, major_diag_flag, minor_diag_flag)

                    board[row * n + col] = '.'
                    col_flag[col] = 1
                    major_diag_flag[row - col] = 1
                    minor_diag_flag[row + col] = 1

解答2

class Solution:
    def totalNQueens(self, n: int) -> int:
        """
            N皇后II(使用 bitmap 回溯)

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            输入: 4
            输出: 2
            解释: 4 皇后问题存在如下两个不同的解法。
            [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
        """

        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()