力扣LeetCode 51. 经典N皇后困难->回溯代码片段

CodeSnippet.Cn
代码片段

Python 小笨蛋发布于：2021年06月30日更新于：2021年06月30日 145

[51. N 皇后](https://leetcode-cn.com/problems/n-queens/ "51. N 皇后")

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

示例 1：
![图片alt](/uploads/images/20210630/222913-a861e7b1e9844f968d19cbcbf5bf1c22.png ''图片title'')
```shell
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
```
示例 2：
```shell
输入：n = 1
输出：[["Q"]]
```

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

> 题解：其实N皇后是非常经典的题目了，网上也有很多解法都大同小异，其关键点就是如何判断出左上与右上是否有Q

```python
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """

res = []
        checkerboard = [['.' for __ in range(n)] for __ in range(n)]

def backtrack(row):
            if row == n:  # 已经到了最后一行
                res.append(["".join(checkerboard[i]) for i in range(n)])
                return

for col in range(n):
                if not self.isValid(row, col, n, checkerboard): continue
                checkerboard[row][col] = 'Q'
                backtrack( row + 1)
                checkerboard[row][col] = '.'

backtrack( 0)

return res

def isValid(self, row, col, n, checkerboard):  # 不能同行，不能同列，不能斜
        # 不能同列
        for i in range(row):
            if checkerboard[i][col] == 'Q':
                return False

return self.checkLeft(row, col, checkerboard) and self.checkRight(row, col, n, checkerboard)

def checkLeft(self, row, col, checkerboard):
        # 左上面不能有斜着的
        while row > 0 and col > 0:
            row -= 1
            col -= 1
            if checkerboard[row][col] == 'Q':
                return False

return True

def checkRight(self, row, col, n, checkerboard):
        # 右上面不能有斜着的
        while row > 0 and col < n - 1:
            row -= 1
            col += 1
            if checkerboard[row][col] == 'Q':
                return False
        return True

if __name__ == '__main__':
    solution = Solution()
    res = solution.solveNQueens(4)
    for i in range(len(res)):
        for j in range(len(res[i])):
            print('|', res[i][j], end='')
        print()

```

这里⇓感觉得写点什么，要不显得有点空，但还没想好写什么... 返回顶部