题目

LeetCode.52.N皇后 II（困难）

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

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

提示：

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

题解

最笨的办法就跟求出N皇后所有选择方案，取选择方案的个数，但这样空间复杂度大，本题只要求方案数，我们得看看空间复杂度能不能降低。

N皇后问题的求解步骤

遍历先所有行
每一行遍历所有列
判断当前列可以放置，进行放置
然后再深度优先搜索，继续放置
直到放置完最后一行

什么情况下需要占用额外空间？

在判断当前行当前列是不是可以放置皇后这个问题上，可能会需要一定的空间记录之前放置过皇后的情况。

怎么判断某一列之前是否已经放置过皇后了？

如果在某一列放置过皇后之后，就把这一列记录下来，到下一行再遍历所有列进行列选择时，就可以查询之前哪些列是放过的，放过的就不在这一列放了。

假设列总数是n，最多也就记录n个列有没有被放过皇后，可以用一个数组保存。

怎么判断当前棋格的左上角和右上角是否已经放置过皇后了？

如果从上往下斜着看，当在上一行第x列放置过皇后之后，我们可以知道下一行的第x + 1列和第x - 1列肯定也不能再放皇后了，因为都处于斜线位置上。

所以在遍历下一行的时候可以直接排除第x + 1列和第x - 1列，就相当于排除了斜线上不能放的位置。

但是到再下一行时，斜线会蔓延到第x + 2列和第x - 2列不可以放皇后。

也就是说斜线上禁止放皇后的位置随着行的增大而平移，位置需要随行保持更新，而且两个方向的斜线更新的方向也不一样。

所以这里需要两个数组存储两个方向斜线列的变化，每增加一行，数组值都要往左和往右移动一个位置。

如何优化空间复杂度？

使用数组记录状态会占用O(n)的空间复杂度。

可以注意到1 <= n <= 9，能够使用二进制的位来记录状态，这样就节省了数组的空间开销，每个状态各自需要一个整数就可以判断，整数总共有32位，足以容纳9个状态值。

怎么用二进制记录三种状态？

用整数变量c的每一位是否是1，表示某一列是否已经已经放过皇后了
用整数变量ld的每一位是否是1，表示某一列的右上角是否已经已经放过皇后了
用整数变量rd的每一位是否是1，表示某一列的左上角是否已经已经放过皇后了

怎么知道哪些列还能放皇后？

具体到某一行时，需要知道哪些列还能放皇后。

哪些列不能放皇后，我们求c、ld、rd三个变量的或的结果q就知道了。

q的二进制中所有为1的位就是已经放过皇后的，不能再放了。

找q中所有为0的位就是可以放皇后的位置；位数不超过n。

0不方便找，也不方便判断，1方便判断，所以可以反过来，把q取反，这样所有为1的位置都是可以放皇后的，但是高位会有多余的1，所以再跟n个1做与操作，把高位多余的1给截取掉。

n个1怎么快速求？可以把1左移n位，再减1。模拟一下就知道。

用bits变量来存储 q取反再跟n个1与操作的结果，bits的某一位为1表示这一位可以放皇后。

怎么遍历所有可以放皇后的列？

依次取bits每一位的1。
遍历何时结束？可以把访问过的1都消除掉，bits为0说明遍历完所有的1了。同时把访问过的1消除掉，也方便取下一个1。

怎么依次取`bits`每一位的1？

可以想办法通过位运算快速求解，充分发挥二进制的优势。

可以每次取最低位的1，我们只要构造一个二进制数，跟bits前面的所有位都相反，就在最后一个1的位置跟bits一样，这样两者做一下与操作就可以得到最低位1。

取反可以想到反码，如果对bits取反，最低位1变成0，接着后面全部都是1，我们可以给反码加1，就可以把最低位的0和1变回来。

反码加1就是补码，所以取-bits跟bits做与操作，得到bits最低位的1。

怎么消除最低位的1？

bits - 1后，最低位1就没了，但是更低位本来全部是0现在都变成1，再跟bits与一下，它们的高位都相同，而bits低位都是0，这样就把bit最低位的1给消除了。

怎么更新`c`、`ld`、`rd`？

取出的bits的最低位的1为pick。

pick二进制中的1代表的列是不能被下一行再访问了，c要多增加这一列的1，c = c or pick 。

pick二进制中的1代表的列的左下方的列在下一行是不能被访问的，并且ld中所有不能访问的列都要左移1位，正好可以用移位运算符很方便的做移动，ld = (ld or pick) shl 1。

pick二进制中的1代表的列的右下方的列在下一行是不能被访问的，并且rd中所有不能访问的列都要右移1位，正好可以用移位运算符很方便的做移动，rd = (rd or pick) shr 1。

class Solution {
    fun totalNQueens(n: Int): Int {
        var count = 0
        
        fun find(row: Int, c: Int, ld: Int, rd: Int) {
            if (row == n) {
                count++
                return
            }
            var bits = (c or ld or rd).inv() and ((1 shl n) - 1)
            while (bits > 0) {
                val pick = bits and -bits
                find(row + 1, c or pick, (pick or ld) shl 1, (pick or rd) shr 1)
                bits = bits and (bits - 1)
            }
        }

        find(0, 0, 0, 0)
        return count
    }
}

题目

题解