51.md

题目地址

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

解答1

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
            N皇后(非最优解)

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
            每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
            输入: 4
            输出: [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
            解释: 4 皇后问题存在两个不同的解法。
        """
        res = []
        if n <= 0:
            return res
        ans = [["." for i in range(n)] for j in range(n)]
        flag = [[0 for i in range(n)] for j in range(n)]
        self.dfs(0, ans, flag, res)
        return res

    def dfs(self, j, ans, flag, res):
        if j == len(ans):
            res.append(["".join(a) for a in ans])
            return
        for i in range(len(ans[0])):
            if not self.checkIJ(flag, i, j):
                continue

            ans[j][i] = "Q"
            from copy import deepcopy
            temp = deepcopy(flag)
            self.setFlag(flag, i, j, len(ans))

            self.dfs(j + 1, ans, flag, res)

            ans[j][i] = "."
            flag = deepcopy(temp)

    def checkIJ(self, flag, i, j):
        if flag[j][i] == 1:
            return False
        return True

    def setFlag(self, flag, i, j, n):
        for l in range(n):
            flag[l][i] = 1
        for k in range(n):
            flag[j][k] = 1
        k, l = i, j
        while i >= 0 and j >= 0:
            flag[j][i] = 1
            i -= 1
            j -= 1
        i, j = k, l
        while i < n and j < n:
            flag[j][i] = 1
            i += 1
            j += 1
        i, j = k, l
        while i < n and j >= 0:
            flag[j][i] = 1
            i += 1
            j -= 1
        i, j = k, l
        while i >= 0 and j < n:
            flag[j][i] = 1
            i -= 1
            j += 1

解答2

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
            N皇后(非最优解)

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
            每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
            输入: 4
            输出: [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
            解释: 4 皇后问题存在两个不同的解法。
        """

        def could_place(row, col):
            return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col])

        def place_queen(row, col):
            queens.add((row, col))
            cols[col] = 1
            hill_diagonals[row - col] = 1
            dale_diagonals[row + col] = 1

        def remove_queen(row, col):
            queens.remove((row, col))
            cols[col] = 0
            hill_diagonals[row - col] = 0
            dale_diagonals[row + col] = 0

        def add_solution():
            solution = []
            for _, col in sorted(queens):
                solution.append('.' * col + 'Q' + '.' * (n - col - 1))
            output.append(solution)

        def backtrack(row=0):
            for col in range(n):
                if could_place(row, col):
                    place_queen(row, col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    remove_queen(row, col)

        cols = [0] * n
        hill_diagonals = [0] * (2 * n - 1)
        dale_diagonals = [0] * (2 * n - 1)
        queens = set()
        output = []
        backtrack()
        return output

解答3

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
            N皇后(非最优解)

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
            每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
            输入: 4
            输出: [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
            解释: 4 皇后问题存在两个不同的解法。
        """
        res = []
        s = "." * n

        def backtrack(i, tmp, col, z_diagonal, f_diagonal):
            if i == n:
                res.append(tmp)
                return
            for j in range(n):
                if j not in col and i + j not in z_diagonal and i - j not in f_diagonal:
                    backtrack(i + 1, tmp + [s[:j] + "Q" + s[j + 1:]], col | {j}, z_diagonal | {i + j},
                              f_diagonal | {i - j})

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

解答4

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
            N皇后

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
            每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
            输入: 4
            输出: [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
            解释: 4 皇后问题存在两个不同的解法。
        """
        board = ['.'] * (n ** 2)
        # can use  `board = [['.'] * n for _ in range(n)]` as well, but need to use `copy.deepcopy` later to copy the list of lists

        res = []

        # flags to indicate whether the a column, a major diagonal or a minor diagonal has been occupied by a Q or not
        col_flag = [1] * n
        major_diag_flag = [1] * (2 * n - 1)
        minor_diag_flag = [1] * (2 * n - 1)

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

        result = []
        for r in res:
            b = []
            for i in range(n):
                b.append(''.join(r[(i * n):((i + 1) * n)]))

            result.append(b)

        return result

    def solve_queue(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):
                # for the square [row, col], it is in major diagonal `n + col - row - 1` and minor diagonal `row + col`
                # this depends on how you count the major and minor diagonals.
                if col_flag[col] and major_diag_flag[n + col - row - 1] and minor_diag_flag[row + col]:
                    board[row * n + col] = 'Q'
                    col_flag[col] = 0
                    major_diag_flag[n + col - row - 1] = 0
                    minor_diag_flag[row + col] = 0

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

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

解答5

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
            N皇后，AC算法

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
            每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
            输入: 4
            输出: [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
            解释: 4 皇后问题存在两个不同的解法。
        """
        ans = []
        queens = [-1] * n
        columns = [True] * n + [False]  # || col with dummy for boundary
        back = [True] * n * 2  # \\ col - row
        forward = [True] * n * 2  # // col + row
        row = col = 0
        while True:
            if columns[col] and back[col - row + n] and forward[col + row]:
                queens[row] = col
                columns[col] = back[col - row + n] = forward[col + row] = False
                row += 1
                col = 0
                if row == n:
                    ans.append(['.' * q + 'Q' + '.' * (n - q - 1) for q in queens])
            else:
                if row == n or col == n:
                    if row == 0:
                        return ans
                    row -= 1
                    col = queens[row]
                    columns[col] = back[col - row + n] = forward[col + row] = True
                col += 1

解答6

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
            N皇后

            n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
            给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
            每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
            输入: 4
            输出: [
             [".Q..",  // 解法 1
              "...Q",
              "Q...",
              "..Q."],

             ["..Q.",  // 解法 2
              "Q...",
              "...Q",
              ".Q.."]
            ]
            解释: 4 皇后问题存在两个不同的解法。
        """

        def DFS(queens, xy_dif, xy_sum):
            p = len(queens)
            if p == n:
                result.append(queens)
                return None
            for q in range(n):
                if q not in queens and p - q not in xy_dif and p + q not in xy_sum:
                    DFS(queens + [q], xy_dif + [p - q], xy_sum + [p + q])

        result = []
        DFS([], [], [])
        return [["." * i + "Q" + "." * (n - i - 1) for i in sol] for sol in result]