# 0052. N皇后 II ## 题目地址(52. N皇后 II) <https://leetcode-cn.com/problems/n-queens-ii/> ## 题目描述 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  ``` <pre class="calibre18">``` 给定一个整数 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 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number} n * @return {number} * @param row 当前层 * @param cols 列 * @param pie 左斜线 * @param na 右斜线 */</span> <span class="hljs-keyword">const</span> totalNQueens = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">let</span> res = <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> dfs = (n, row, cols, pie, na) => { <span class="hljs-keyword">if</span> (row >= n) { res++; <span class="hljs-keyword">return</span>; } <span class="hljs-title">// 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历</span> <span class="hljs-title">// 也就是得到当前所有的空位</span> <span class="hljs-keyword">let</span> bits = (~(cols | pie | na)) & ((<span class="hljs-params">1</span> << n) - <span class="hljs-params">1</span>); <span class="hljs-keyword">while</span> (bits) { <span class="hljs-title">// 取最低位的1</span> <span class="hljs-keyword">let</span> p = bits & -bits; <span class="hljs-title">// 把P位置上放入皇后</span> bits = bits & (bits - <span class="hljs-params">1</span>); <span class="hljs-title">// row + 1 搜索下一行可能的位置</span> <span class="hljs-title">// cols ｜ p 目前所有放置皇后的列</span> <span class="hljs-title">// (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置</span> dfs(n, row + <span class="hljs-params">1</span>, cols | p, (pie | p) << <span class="hljs-params">1</span>, (na | p) >> <span class="hljs-params">1</span>); } } dfs(n, <span class="hljs-params">0</span>, <span class="hljs-params">0</span>, <span class="hljs-params">0</span>, <span class="hljs-params">0</span>); <span class="hljs-keyword">return</span> res; }; ``` ``` ***复杂度分析*** - 时间复杂度：O(N!) - 空间复杂度：O(N)