Hard

题目描述

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

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

示例 1：

输入：n = 4
输出：2
解释：4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

  • 1 <= n <= 9

解题思路

解题思路

这是经典的 N 皇后问题的变种，只需要统计解的数量而不需要返回具体的解。

核心思想是回溯算法：

  1. 逐行放置皇后，每行只能放一个皇后
  2. 对于每一行，尝试在每一列放置皇后
  3. 检查当前位置是否与之前放置的皇后冲突
  4. 如果不冲突，继续递归下一行；如果冲突，回溯尝试下一个位置

冲突检查规则：

  • 同一列不能有两个皇后
  • 同一对角线（主对角线和反对角线）不能有两个皇后

优化技巧： 可以用三个集合分别记录已占用的列、主对角线和反对角线，避免重复计算。对于位置 (i,j)：

  • 列索引：j
  • 主对角线索引：i-j
  • 反对角线索引：i+j

当成功放置 n 个皇后时，找到一个解，计数器加一。

代码实现

class Solution {
public:
    int totalNQueens(int n) {
        vector<bool> cols(n, false);
        vector<bool> diag1(2 * n - 1, false);
        vector<bool> diag2(2 * n - 1, false);
        
        return backtrack(0, n, cols, diag1, diag2);
    }
    
private:
    int backtrack(int row, int n, vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2) {
        if (row == n) {
            return 1;
        }
        
        int count = 0;
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1;
            int d2 = row + col;
            
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                cols[col] = diag1[d1] = diag2[d2] = true;
                count += backtrack(row + 1, n, cols, diag1, diag2);
                cols[col] = diag1[d1] = diag2[d2] = false;
            }
        }
        
        return count;
    }
};

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row, cols, diag1, diag2):
            if row == n:
                return 1
            
            count = 0
            for col in range(n):
                d1 = row - col
                d2 = row + col
                
                if col not in cols and d1 not in diag1 and d2 not in diag2:
                    cols.add(col)
                    diag1.add(d1)
                    diag2.add(d2)
                    
                    count += backtrack(row + 1, cols, diag1, diag2)
                    
                    cols.remove(col)
                    diag1.remove(d1)
                    diag2.remove(d2)
            
            return count
        
        return backtrack(0, set(), set(), set())

public class Solution {
    public int TotalNQueens(int n) {
        bool[] cols = new bool[n];
        bool[] diag1 = new bool[2 * n - 1];
        bool[] diag2 = new bool[2 * n - 1];
        
        return Backtrack(0, n, cols, diag1, diag2);
    }
    
    private int Backtrack(int row, int n, bool[] cols, bool[] diag1, bool[] diag2) {
        if (row == n) {
            return 1;
        }
        
        int count = 0;
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1;
            int d2 = row + col;
            
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                cols[col] = diag1[d1] = diag2[d2] = true;
                count += Backtrack(row + 1, n, cols, diag1, diag2);
                cols[col] = diag1[d1] = diag2[d2] = false;
            }
        }
        
        return count;
    }
}

var totalNQueens = function(n) {
    let count = 0;
    
    function backtrack(row, cols, diag1, diag2) {
        if (row === n) {
            count++;
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
                continue;
            }
            
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            
            backtrack(row + 1, cols, diag1, diag2);
            
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }
    
    backtrack(0, new Set(), new Set(), new Set());
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N!)第一行有 N 种选择，第二行最多 N-1 种选择，以此类推
空间复杂度O(N)递归调用栈深度为 N，辅助数组空间为 O(N)

相关题目