# 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)