LeetCode 51. N 皇后

Categories:

题目描述
思路分析
1. 解法一：回溯 + 集合剪枝（推荐）
2. 解法二：回溯 + 位运算剪枝
相似题目

题目描述

✅ 51. N 皇后

思路分析

解法一：回溯 + 集合剪枝（推荐）

核心思路：

逐行放置皇后，对每一行枚举所有列位置，若当前位置合法则递归到下一行。

用三个集合记录已被占用的列、主对角线（row - col 相同）、副对角线（row + col 相同），O(1) 判断冲突。

当所有 n 行都放置完毕时，将当前棋盘转换为字符串列表加入结果。

回溯时撤销当前行的放置，继续枚举其他列位置。

复杂度分析：

时间复杂度：O(n!)，其中 n 为皇后数量，最坏情况下需要枚举所有合法排列

空间复杂度：O(n)，其中 n 为递归深度及辅助集合空间

class Solution {

    private List<List<String>> result = new ArrayList<>();
    // 已占用的列
    private Set<Integer> cols = new HashSet<>();
    // 已占用的主对角线（row - col 相同）
    private Set<Integer> diag1 = new HashSet<>();
    // 已占用的副对角线（row + col 相同）
    private Set<Integer> diag2 = new HashSet<>();

    public List<List<String>> solveNQueens(int n) {
        // 使用字符数组记录每行皇后的列位置
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        backtrack(queens, n, 0);
        return result;
    }

    private void backtrack(int[] queens, int n, int row) {
        // 所有行均已放置完毕，生成棋盘并加入结果
        if (row == n) {
            result.add(generateBoard(queens, n));
            return;
        }
        for (int col = 0; col < n; col++) {
            // 列、主对角线、副对角线均未被占用时放置皇后
            if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) {
                continue;
            }
            queens[row] = col;
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            backtrack(queens, n, row + 1);
            // 回溯：撤销当前行的放置
            queens[row] = -1;
            cols.remove(col);
            diag1.remove(row - col);
            diag2.remove(row + col);
        }
    }

    private List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

func solveNQueens(n int) [][]string {
    var result [][]string
    queens := make([]int, n)
    for i := range queens {
        queens[i] = -1
    }
    // 已占用的列
    cols := make(map[int]bool)
    // 已占用的主对角线（row - col 相同）
    diag1 := make(map[int]bool)
    // 已占用的副对角线（row + col 相同）
    diag2 := make(map[int]bool)

    var backtrack func(row int)
    backtrack = func(row int) {
        // 所有行均已放置完毕，生成棋盘并加入结果
        if row == n {
            result = append(result, generateBoard(queens, n))
            return
        }
        for col := 0; col < n; col++ {
            // 列、主对角线、副对角线均未被占用时放置皇后
            if cols[col] || diag1[row-col] || diag2[row+col] {
                continue
            }
            queens[row] = col
            cols[col] = true
            diag1[row-col] = true
            diag2[row+col] = true
            backtrack(row + 1)
            // 回溯：撤销当前行的放置
            queens[row] = -1
            cols[col] = false
            diag1[row-col] = false
            diag2[row+col] = false
        }
    }
    backtrack(0)
    return result
}

func generateBoard(queens []int, n int) []string {
    board := make([]string, n)
    for i := 0; i < n; i++ {
        row := make([]byte, n)
        for j := range row {
            row[j] = '.'
        }
        row[queens[i]] = 'Q'
        board[i] = string(row)
    }
    return board
}

解法二：回溯 + 位运算剪枝

核心思路：

用三个整数的二进制位分别表示列、主对角线、副对角线的占用状态，位运算替代集合，速度更快。

cols | diag1 | diag2 的 OR 结果中，值为 1 的位表示当前行不可放置的列位置。

取反后与 (1 << n) - 1 做 AND，得到当前行所有可选列的候选位掩码。

每次取最低位的 1（candidate & -candidate）作为当前列，清除后继续枚举。

向下递归时对角线掩码左移/右移一位即可对齐到下一行。

复杂度分析：

时间复杂度：O(n!)，其中 n 为皇后数量，位运算加速了常数因子

空间复杂度：O(n)，其中 n 为递归深度及辅助数组空间

class Solution {

    private List<List<String>> result = new ArrayList<>();
    private int[] queens;
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.queens = new int[n];
        Arrays.fill(queens, -1);
        // 全部 n 列均可用，掩码低 n 位全为 1
        int fullMask = (1 << n) - 1;
        backtrack(0, 0, 0, 0, fullMask);
        return result;
    }

    private void backtrack(int row, int cols, int diag1, int diag2, int fullMask) {
        if (row == n) {
            result.add(generateBoard());
            return;
        }
        // 取当前行所有可放置的列位掩码
        int available = fullMask & ~(cols | diag1 | diag2);
        while (available != 0) {
            // 取最低位的 1，即当前最优先尝试的列
            int bit = available & -available;
            available -= bit;
            // Integer.numberOfTrailingZeros 将位转换为列索引
            queens[row] = Integer.numberOfTrailingZeros(bit);
            backtrack(
                row + 1,
                cols | bit,
                // 主对角线掩码左移一行
                (diag1 | bit) << 1,
                // 副对角线掩码右移一行
                (diag2 | bit) >> 1,
                fullMask
            );
            queens[row] = -1;
        }
    }

    private List<String> generateBoard() {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

func solveNQueens(n int) [][]string {
    var result [][]string
    queens := make([]int, n)
    for i := range queens {
        queens[i] = -1
    }
    // 全部 n 列均可用，掩码低 n 位全为 1
    fullMask := (1 << n) - 1

    var backtrack func(row, cols, diag1, diag2 int)
    backtrack = func(row, cols, diag1, diag2 int) {
        if row == n {
            result = append(result, generateBoard(queens, n))
            return
        }
        // 取当前行所有可放置的列位掩码
        available := fullMask & ^(cols | diag1 | diag2)
        for available != 0 {
            // 取最低位的 1，即当前最优先尝试的列
            bit := available & -available
            available -= bit
            // bits.TrailingZeros 将位转换为列索引
            queens[row] = bits.TrailingZeros(uint(bit))
            backtrack(
                row+1,
                cols|bit,
                // 主对角线掩码左移一行
                (diag1|bit)<<1,
                // 副对角线掩码右移一行
                (diag2|bit)>>1,
            )
            queens[row] = -1
        }
    }
    backtrack(0, 0, 0, 0)
    return result
}

func generateBoard(queens []int, n int) []string {
    board := make([]string, n)
    for i := 0; i < n; i++ {
        row := make([]byte, n)
        for j := range row {
            row[j] = '.'
        }
        row[queens[i]] = 'Q'
        board[i] = string(row)
    }
    return board
}

相似题目

题目	难度	考察点
52. N 皇后 II	困难	回溯、位运算
37. 解数独	困难	回溯、约束传播
46. 全排列	中等	回溯、数组
47. 全排列 II	中等	回溯、去重
79. 单词搜索	中等	回溯、DFS
131. 分割回文串	中等	回溯、动态规划
212. 单词搜索 II	困难	回溯、字典树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/68253214