52. N皇后 II

[Geekhyt]

原题链接

如果你想对位运算了解更多，请稍移玉步

皇后可以横、直、斜走，格数不限。题目要求皇后彼此之间不能相互攻击，也就是说需要满足任意两个皇后不能在同一行、同一列以及同一条斜线上。

熟悉这道题的同学，可以看出最直观的做法是利用回溯法进行求解。

遍历枚举出所有可能的选择，依次在每一行放置一个皇后，每次新放置的皇后不能和已经放置的皇后之间存在攻击。

为了降低时间复杂度，最理想的情况是在 O(1) 的时间内判断该位置所在的几条线上是否已经有皇后，可以利用集合来进行位置判断。

为了让你更好的理解，我利用回溯法将 4 皇后可能的解法画了出来。如下图所示：

下面这张图是两条对角线方向的斜线的规律，聪明的你肯定一眼就能看出来：

一句话理解四种算法思想

• 分治：分而治之，先解决子问题，再将子问题的解合并求出原问题。
• 贪心：一条路走到黑，选择当下局部最优的路线，没有后悔药。
• 回溯：一条路走到黑，手握后悔药，可以无数次重来。(英雄联盟艾克大招无冷却)。
• 动态规划：上帝视角，手握无数平行宇宙的历史存档，同时发展出无数个未来。

位运算回溯

先来明确几个概念和需要用到的公式：

• n：n层
• row：当前层
• cols：列
• pie：撇，左斜线(副对角线)
• na：捺，右斜线(正对角线)
• 二进制为 1，代表不可放置，0 相反
• x & -x ：得到最低位的1 (代表除最后一位 1 保留，其他位全部为 0)
• x & (x - 1)：清零最低位的 1 (代表将最后一位 1 变成 0)
• x & ((1 << n) - 1)：将 x 的最高位至第 n 位(含)清零

将 N 个位置对应成 N 个二进制位，0 代表可以选择，1 代表不能选择。

比如八皇后当前第一行的第二位被选择时的状态是 00100000，那么下一行的第二位也不能被选择，正对角线(na)对应的第三位不能被选择(对应当前行右移了一位)，状态表示为：00100000。副对角线(pie)对应的第一位不能被选择(对应当前行左移了一位)，状态表示为 10000000。

const totalNQueens = function(n) {
    let res = 0
    const dfs = (n, row, cols, pie, na) => {
        if (row >= n) {
            res++
            return
        }
        let bits = (~(cols | pie | na)) & ((1 << n) - 1) // 1
        while (bits) { // 2
            let p = bits & -bits // 3
            dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1) // 4
            bits = bits & (bits - 1) // 5
        }
    }
    dfs(n, 0, 0, 0, 0)
    return res
}

• 时间复杂度：O(N!)
• 空间复杂度：O(N)

代码解读

1.cols ｜ pie ｜ na 表示所有能够被皇后攻击的格子，~(cols | pie | na)取反表示将没有被占的格子从 0 变为 1，以便后续的位遍历。这里用到公式：x & ((1 << n) - 1)：将 x 的最高位至第 n 位(含)清零。一个 int 的二进制位至少有 32 位，我们将前面不需要的位置清零。所以，这行代码表示得到当前所有的空位，也就是可以放置皇后的格子。

2.只要 bits 中有 1，就说明还有格子可以放置皇后，每次遍历都会将其清零(表示在p位置放入了皇后)，也就是注释 5 的代码含义。对应公式：x & (x - 1)：清零最低位的 1 (代表将最后一位 1 变成 0)。

3.对应公式：x & -x ：得到最低位的1 (代表除最后一位 1 保留，其他位全部为 0)，表示当前皇后可放入的位置。

4.修改状态，进入下一层递归。row + 1 代表搜索下一行，cols ｜ p 代表目前所有可以放置皇后的列。(pie | p) << 1 ，(na | p) >> 1，在上面思路中已经说过了，不再赘述。