LeetCode 52 - N皇后 II（N-Queens II）

问题描述

N皇后 II 是 N皇后问题的延伸。不同的是，这道题只需要返回不同解决方案的数量，而不需要返回具体的解决方案。

与N皇后问题相同，规则如下：

皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子
需要将N个皇后放置在N×N的棋盘上，使皇后彼此不能相互攻击
给你一个整数N，返回所有不同解决方案的数量

示例 1

输入：n = 4
输出：2

解释：如同N皇后问题所示，4皇后问题共有两种解法。

示例 2

输入：n = 1
输出：1

约束条件

1 <= n <= 9

解题思路

这道题与N皇后问题的核心算法相同，区别在于：

不需要记录棋盘的具体摆放方式
只需要计算解的数量
可以更进一步使用位运算优化空间复杂度

基础解法

基础解法与N皇后问题类似，使用回溯算法：

使用三个布尔数组记录行、主对角线、副对角线的占用情况
按列递归，对于每一列尝试在各行放置皇后
当成功放置N个皇后时，解的计数器加1
回溯过程中撤销对行和对角线的标记

此处我们直接跳过具体的棋盘表示，仅使用计数器记录解的数量。

位运算优化

核心洞见：我们可以使用整数的二进制位代替布尔数组，进一步优化空间复杂度。

在位运算解法中：

使用一个整数的二进制位表示每一行是否已放置皇后
同样使用整数表示主对角线和副对角线的占用情况
通过位操作高效地检查位置可用性和更新状态

位运算的关键操作：

检查位置可用性：(~(rows | diags1 | diags2)) & (1 << i)
标记占用：rows |= (1 << i)
撤销标记：rows &= ~(1 << i)

实现细节

标准回溯实现

与N皇后问题相比，我们不再需要构建棋盘，只需计数：

func totalNQueens(n int) int {
    // 标记数组，记录已占用的行和对角线
    rowUsed := make([]bool, n)          // 标记行是否已被占用
    mainDiagUsed := make([]bool, 2*n)   // 标记主对角线是否已被占用
    subDiagUsed := make([]bool, 2*n)    // 标记副对角线是否已被占用
    
    // 解的计数器
    count := 0
    
    // DFS函数，col表示当前处理的列
    var dfs func(col int)
    dfs = func(col int) {
        // 如果所有列都已处理，找到一个解
        if col == n {
            count++
            return
        }
        
        // 尝试在当前列的每一行放置皇后
        for row := 0; row < n; row++ {
            // 检查位置(row, col)是否安全
            if rowUsed[row] || mainDiagUsed[row+col] || subDiagUsed[n+row-col] {
                continue
            }
            
            // 标记占用
            rowUsed[row] = true
            mainDiagUsed[row+col] = true
            subDiagUsed[n+row-col] = true
            
            // 递归处理下一列
            dfs(col + 1)
            
            // 回溯：撤销标记
            rowUsed[row] = false
            mainDiagUsed[row+col] = false
            subDiagUsed[n+row-col] = false
        }
    }
    
    // 从第0列开始DFS
    dfs(0)
    return count
}

位运算优化实现

现在，让我们使用位运算来优化解法：

func totalNQueens(n int) int {
    // 解的计数器
    count := 0
    
    // 使用位运算实现的DFS
    var dfs func(col, rows, diags1, diags2 int)
    dfs = func(col, rows, diags1, diags2 int) {
        // 完成了N列的放置，找到一个解
        if col == n {
            count++
            return
        }
        
        // 计算当前列所有可放置皇后的位置
        // ~(rows | diags1 | diags2) 表示所有可用的位置（值为1的位）
        // & ((1 << n) - 1) 确保只考虑棋盘范围内的位（n位）
        availablePositions := ^(rows | diags1 | diags2) & ((1 << n) - 1)
        
        // 逐一尝试可放置的位置
        for availablePositions > 0 {
            // 获取最低位的1（表示一个可放置的位置）
            position := availablePositions & -availablePositions
            
            // 将这个位从可用位置中移除
            availablePositions ^= position
            
            // 递归处理下一列
            // rows | position: 更新已占用的行
            // (diags1 | position) << 1: 更新主对角线，左移模拟对角线移动
            // (diags2 | position) >> 1: 更新副对角线，右移模拟对角线移动
            dfs(col+1, rows|position, (diags1|position)<<1, (diags2|position)>>1)
            
            // 不需要显式回溯，因为我们传递的是值而不是引用
        }
    }
    
    // 从第0列开始，初始时所有行和对角线都未被占用（都是0）
    dfs(0, 0, 0, 0)
    return count
}

位运算解法详解

位运算可能不那么直观，让我们详细解释其工作原理：

状态表示

在位运算解法中，我们使用整数的二进制位来表示各行和对角线的占用情况：

rows：第i位表示第i行是否已放置皇后
diags1：表示主对角线（左上至右下）的占用情况
diags2：表示副对角线（右上至左下）的占用情况

位操作解释

检查可用位置：
1
availablePositions := ^(rows | diags1 | diags2) & ((1 << n) - 1)
- rows | diags1 | diags2：合并所有被占用的位
- ^：按位取反，将0变为1，1变为0，这样1就表示可用位置
- & ((1 << n) - 1)：保留低n位，其他位置为0（因为棋盘大小为n）
获取一个可放置位置：
1
position := availablePositions & -availablePositions
- availablePositions & -availablePositions：获取最低位的1，这是一个常用技巧
- 例如，如果 availablePositions = 1010，则 -availablePositions = 0110（二进制补码），availablePositions & -availablePositions = 0010
移除已使用的位置：
1
availablePositions ^= position
- ^=：按位异或，将已用位置从可用位置中移除
更新状态并递归：
1
dfs(col+1, rows|position, (diags1|position)<<1, (diags2|position)>>1)
- rows|position：标记行为已使用
- (diags1|position)<<1：更新并左移主对角线占用状态
- (diags2|position)>>1：更新并右移副对角线占用状态

位运算示例

以棋盘大小n=4为例，显示第一步的操作：

初始状态：
- rows = 0000（所有行未占用）
- diags1 = 0000（所有主对角线未占用）
- diags2 = 0000（所有副对角线未占用）
检查第0列可放置位置：
- 所有行都可用，availablePositions = 1111
尝试在第0行第0列放置皇后：
- position = 0001（第0行）
- 更新状态：
  - rows = 0001
  - diags1 = 0010（左移）
  - diags2 = 0000（右移，最低位丢失）
检查第1列可放置位置：
- rows | diags1 | diags2 = 0011
- 可用位置 = ~0011 & 1111 = 1100（第2行和第3行）

依此类推，回溯过程会尝试所有可能的放置方式。

复杂度分析

时间复杂度

两种实现的时间复杂度都是 $O(N!)$，因为：

第一列有N个位置可选
第二列最多有N-1个位置可选
第三列最多有N-2个位置可选
以此类推

实际上，由于剪枝的存在，实际运行时间会小于 $O(N!)$。

空间复杂度

标准回溯解法：
- 空间复杂度为 $O(N)$，主要是三个标记数组和递归调用栈
位运算解法：
- 空间复杂度为 $O(1)$，因为我们只使用固定的几个整数来表示状态
- 这是位运算解法的主要优势之一

注意：位运算解法的空间优势在N很大时更加明显。但当N > 32（或在64位系统上N > 64）时，单个整数的位数不足以表示所有状态，可能需要使用大整数库或其他方法。

方法比较

方面	标准回溯解法	位运算解法
时间复杂度	O(N!)	O(N!)
空间复杂度	O(N)	O(1)
优点	直观易懂	空间效率高，常数操作更快
缺点	空间消耗较大	可读性较差，仅适用于N≤32或64
适用场景	教学演示、代码可读性要求高	空间受限、追求极致性能

关键收获

回溯与位运算结合：N皇后问题展示了如何将位运算与回溯算法结合，优化空间复杂度。
位运算技巧：
- 使用单个整数的二进制位表示多个布尔值
- 使用 x & -x 获取最低位的1
- 使用位移操作模拟数据结构的变化
算法优化思路：有时不需要记录具体解的内容，只需记录解的数量，可以大幅简化代码和优化性能。
两类问题的关联：N皇后I和N皇后II展示了两种常见的问题变体——“求所有解"和"求解的数量”，它们通常可以用相同的核心算法解决，但后者往往有额外的优化空间。

位运算解法虽然在这个问题中能带来空间效率的提升，但也增加了代码复杂度和理解难度。在实际应用中，需要根据具体情况（如N的大小、性能要求、代码可维护性等）选择合适的实现方法。