题解 | #N皇后问题#

位运算辅助加快计算

class Solution: 
    # 皇后个数上限 当前行皇后列限制 当前行左斜线限制 当前行右斜线限制 
    def backtrack(self,upperLim,colLim,leftDialim,rightDialim):
        # 如果当前行皇后列限制等于皇后个数上限 即 colLim 也全为1 则代表棋盘上已经有n个皇后了 满足条件 结果加1
        if colLim == upperLim:
            return 1
        # 合并所有限制位置并取反,寻找可以放置皇后的位置
        pos = upperLim & (~(colLim | leftDialim | rightDialim))
        # 结果数
        res = 0
        # 如果存在可以放皇后的位置 即 pos的二进制位不全为0 即 pos不为0
        while pos != 0:
            # 取最右侧的可放皇后的位置
            mostRightOne = pos & (~pos + 1)
            # 去掉最右侧可放皇后的位置
            pos = pos - mostRightOne
            # 递归调用取下一个可放皇后的位置 下一行的列限制为(当前行列限制+新取皇后所在列) 下一行左斜线限制为(当前行左斜线限制+新取皇后所在列)整体左移1位 下一行右斜线限制为(当前行右斜线限制+新取皇后所在列)整体右移1位 
            res += self.backtrack(upperLim, colLim | mostRightOne, (leftDialim | mostRightOne) << 1,
                            (rightDialim | mostRightOne) >> 1)
        return res
        
    
    def Nqueen(self , n: int) -> int:
        if n < 1 or n > 32:
            return 0
        # 皇后每行最多只有一个 将n行棋盘映射为二进制 n个1
        upperLim = -1 if n==32 else (1<<n) -1
        return self.backtrack(upperLim,0,0,0)
            
        # write code here