# \[51]\[困难]\[回溯] N皇后

## 题目描述

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

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

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

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

示例 1：

![](/files/-MWIZOym4intDBzihShH)

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

示例 2：

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

提示：

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

## 解题思路

N皇后是典型的回溯问题. N个皇后摆放在棋盘上, 相互之间不能攻击, 因此我们需要尝试依次摆放每个棋子, 前面摆放的棋子都后续的摆放产生了限制.

为了快速查询当前位置能否摆放棋子, 我们记录每行, 每列, 每条对角线和反对角线是否已经被占用.

行和列容易记录, 两种对角线的记录方式绕一些. 对于n \* n的棋盘, 它的对角线和反对角线各有2n - 1条, 其中:

* 同一条对角线位置的横纵坐标相减恒定, 即`i-j`不变
* 反对角线的横纵坐标之和恒定, 即`i+j`不变

这样我们就可以创建4个数组, 分别记录每行, 每列, 每条对角线和反对角线是否已经被占用.

遍历时从某个坐标出发, 向四周搜索, 是最简单的搜索方法. 但这种方法复杂度高, 最坏的情况下, 每个皇后都要遍历所有棋盘位置才能确定. 提交后超时.

```python
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n == 1:
            return [['Q']]

        board = [['.'] * n for _ in range(n)]
        row = [False] * n
        col = [False] * n
        diagonal = {i: False for i in range(-(n - 1), n)}
        back_diagonal = {i: False for i in range((n - 1) * 2 + 1)}
        seen = [[False] * n for _ in range(n)]
        res = set()

        def dfs(i, j, count):
            if count == n:
                res.add('|'.join([''.join(t) for t in board]))
                return

            seen[i][j] = True
            if not row[i] and not col[j] and not diagonal[i - j] and not back_diagonal[i + j]:
                row[i] = col[j] = diagonal[i - j] = back_diagonal[i + j] = True
                board[i][j] = 'Q'
                if 0 <= i - 1 < n and not seen[i - 1][j]:
                    dfs(i - 1, j, count + 1)
                if 0 <= i + 1 < n and not seen[i + 1][j]:
                    dfs(i + 1, j, count + 1)
                if 0 <= j - 1 < n and not seen[i][j - 1]:
                    dfs(i, j - 1, count + 1)
                if 0 <= j + 1 < n and not seen[i][j + 1]:
                    dfs(i, j + 1, count + 1)
                board[i][j] = '.'
                row[i] = col[j] = diagonal[i - j] = back_diagonal[i + j] = False

            if 0 <= i - 1 < n and not seen[i - 1][j]:
                dfs(i - 1, j, count)
            if 0 <= i + 1 < n and not seen[i + 1][j]:
                dfs(i + 1, j, count)
            if 0 <= j - 1 < n and not seen[i][j - 1]:
                dfs(i, j - 1, count)
            if 0 <= j + 1 < n and not seen[i][j + 1]:
                dfs(i, j + 1, count)

            seen[i][j] = False

        dfs(0, 0, 0)
        return [t.split('|') for t in res]
```

而我们知道, 每行有且只能有一个皇后, 因此可以按行探索, 每行内搜索所有可能摆放皇后的位置, 遍历完毕后, 探索下一行, 直到所有行探索完毕, 也就得到了所有可能的结果. 因此我们不再需要记录每一行是否被占用了, 而是记录每一行对应的皇后棋子摆放列的索引.

```python
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:    
        row = [-1] * n
        col = [False] * n
        diagonal = {i: False for i in range(-(n - 1), n)}
        back_diagonal = {i: False for i in range((n - 1) * 2 + 1)}
        res = []

        def dfs(i):
            if i == n:
                t_res = []
                for k in range(n):
                    tmp = ['.'] * n
                    tmp[row[k]] = 'Q'
                    t_res.append(''.join(tmp))
                res.append(t_res)
                return

            for j in range(n):
                if col[j] or diagonal[i - j] or back_diagonal[i + j]:
                    continue
                row[i] = j
                col[j] = diagonal[i - j] = back_diagonal[i + j] = True
                dfs(i + 1)
                col[j] = diagonal[i - j] = back_diagonal[i + j] = False

        dfs(0)
        return res
```

## 参考资料

* [N皇后](https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/hui-su/51n-huang-hou.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.