LeetCode-每日练习：N皇后问题

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

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

class Solution:
    # 判断当前row、col放置是否与之前放置的皇后冲突
    def isValid(self, n:int, row: int, col: int, chessboard: List[List[str]]):
        # 同一列是否已经放置
        for i in range(row):
            if chessboard[i][col] == 'Q':
                return False

        # 在左上对角线是否已经放置
        i = row - 1
        j = col - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == 'Q':
                return False
            i -= 1
            j -= 1

        # 在右上对角线是否已经放置
        i = row - 1
        j = col + 1
        while j >= 0 and j < n:
            if chessboard[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        # 如果满足放置条件则直接放置
        return True

    def solveNQueens(self, n: int) -> List[List[str]]:
        # 定义一个初始化棋盘
        chessboard = [['.' for _ in range(n)] for _ in range(n)]
        # 
        res = []
        # 定义回溯函数,放置第 row 行的皇后
        def backtrace(chessboard: List[List[str]], row: int):
            # 递归的终止条件：到最后一行
            if row == n:
                path = []
                for ch in chessboard:
                    row_str = ''.join(ch)
                    path.append(row_str)
                res.append(path)
                return 
            
            for col in range(n):
                # 判断该位置放置皇后之后与之前放置的皇后不冲突
                if self.isValid(n, row, col, chessboard):
                    chessboard[row][col] = 'Q'
                    backtrace(chessboard, row + 1)
                    chessboard[row][col] = '.'
        backtrace(chessboard, 0)
        return res