51. N 皇后

Difficulty
Hard
Tags
回溯
URL
https://leetcode-cn.com/problems/n-queens/
Star
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
notion imagenotion image
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
  • 1 <= n <= 9
  • 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
通过次数148,397提交次数200,789

回溯

思路
对每一行用递归来向下搜索
对每一列采用递归里面的for循环填充，填充完一个格，判断是否合法，如果合法就向下一层
题解
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.res = []
        path = ['.'*n for _ in range(n)]
        self.backtrack(path=path, row=0, n=n)
        return self.res

    def backtrack(self, path, row, n):
        if row >= n:
            self.res.append(path[:])
            return
        
        for i in range(0, n):
            # 将 row行 第 i g个置为 Q,判断是否合法
            if self.valid(path, row, i):
                path[row] = path[row][0:i] + 'Q' + path[row][i+1:]
                self.backtrack(path, row+1, n)
                path[row] = '.'*n
    def valid(self, path, row, col):
        # 如果是第一行，肯定合法
        if row == 0:
            return True
        # 先判断 当前列正上方有无Q
        for i in range(0, row):
            if path[i][col] == 'Q':
                return False
        # 判断左上方
        i, j = row-1, col-1
        while i >=0 and j >= 0: 
            if path[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # 判断右上方
        i, j = row -1, col + 1
        while i >= 0 and j < len(path):
            if path[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True