# 0052. N 皇后 II
### 题目地址(52. N皇后 II)
### 题目描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
```
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
```
### 前置知识
* 回溯
* 深度优先遍历
### 公司
* 阿里
* 百度
* 字节
### 思路
使用深度优先搜索配合位运算，二进制为 1 代表不可放置，0 相反
利用如下位运算公式：
* x & -x ：得到最低位的 1 代表除最后一位 1 保留，其他位全部为 0
* x & (x-1)：清零最低位的 1 代表将最后一位 1 变成 0
* x & ((1 << n) - 1)：将 x 最高位至第 n 位(含)清零
### 关键点
* 位运算
* DFS（深度优先搜索）
### 代码
* 语言支持：JS
```js
/**
* @param {number} n
* @return {number}
* @param row 当前层
* @param cols 列
* @param pie 左斜线
* @param na 右斜线
*/
const totalNQueens = function (n) {
let res = 0;
const dfs = (n, row, cols, pie, na) => {
if (row >= n) {
res++;
return;
}
// 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
// 也就是得到当前所有的空位
let bits = (~(cols | pie | na)) & ((1 << n) - 1);
while (bits) {
// 取最低位的1
let p = bits & -bits;
// 把P位置上放入皇后
bits = bits & (bits - 1);
// row + 1 搜索下一行可能的位置
// cols ｜ p 目前所有放置皇后的列
// (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置
dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
}
}
dfs(n, 0, 0, 0, 0);
return res;
};
```
***复杂度分析***
* 时间复杂度：O(N!)
* 空间复杂度：O(N)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/52.n-queens-ii.md?ask=
```
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.