51. N 皇后-Hard.md

Description

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9
• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

Solution

• 该题和[[46. 全排列-Medium]]框架类似，主框架下初始化一个没放置皇后的棋盘，并且进行回溯。每一次回溯相当于对棋盘中的一行做选择，回溯内部对该行的所有列做遍历。

  这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后

• 在此基础上需要额外写一个isValid函数判断 是否可以在 board[row][col] 放置皇后（剪枝）。即判断之前的行、列和斜线是否已经有皇后（但行不用判断，因为是按行做的回溯）
• 时间复杂度：$O(n*n!)$
• 空间复杂度：$O(n)$

class Solution:
    # 是否可以在 board[row][col] 放置皇后？
    def isValid(self, board, row, col):
        n = len(board)
        # 检查列是否有皇后互相冲突
        for i in range(n):
            if board[i][col] == 'Q':
                return False
        # 检查右上方是否有皇后互相冲突
        i = row - 1
        j = col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1

        # 检查左上方是否有皇后互相冲突
        i = row - 1
        j = col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1

        return True

    def solveNQueens(self, n: int) -> List[List[str]]:
        self.res = []
        board = ['.'*n for i in range(n)]
        self.backtrack(0, board)
        return self.res
 
    def backtrack(self, row, board):
        if row == len(board):
            self.res.append(board.copy())
            return
        
        for col in range(len(board)):
            if not self.isValid(board, row, col):
                continue
            board[row] = board[row][:col] + 'Q' + board[row][col+1:]
            self.backtrack(row+1, board)
            board[row] = board[row][:col] + '.' + board[row][col+1:]