LeetCode 面试题 08.12. 八皇后

约 6 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 程序员面试金典（第 6 版） 腾讯 字节 微软 快手
标签
数组 回溯

题目描述

✅ 面试题 08.12. 八皇后

image-20260928225332891

题意分析

在 n×n 棋盘上放 n 个互不攻击的皇后，返回全部布局。皇后不能同行、同列，也不能处于任意一条对角线上；题目名称是八皇后，实际棋盘大小由 n 决定。

n 个皇后分布在 n 行且不能同行，所以每行恰好放一个。搜索只需逐行选择列，不必枚举任意格子组合。

解法：按行回溯 + 三组占用标记

核心思路

[!blue]

用 dfs(row) 为第 row 行选择皇后的位置。进入这一层时，前 row 行各有一个皇后且彼此不冲突，当前行及之后都为空；三个占用数组只记录这些已放皇后。

同一条主对角线上的格子满足 row-col 相等，同一条副对角线满足 row+col 相等。前者加上 n-1 后，两类编号都落在 [0, 2n-2]，因此各用长度 2n-1 的数组即可。候选位置的列和两个对角线都未占用时，放下皇后不会与前面的皇后冲突，能够继续处理下一行。

每次递归返回，都撤销本次放置及三个标记，恢复进入该分支之前的状态，再尝试下一列。到达 row == n 时，恰好放完 n 个互不攻击的皇后，将棋盘转为字符串快照保存。

每个合法布局在每一行都有唯一的列选择，这条路径不会被冲突检查剪掉，因此不会漏解；不同选择路径至少有一行不同，也不会重复收集。某行无处可放时直接返回，由上一行改选位置。

解题步骤

  1. 初始化全为 . 的棋盘，以及列、主对角线、副对角线三个占用数组。
  2. 在第 row 行依次尝试每个 col，计算两个对角线编号。
  3. 任一编号已占用就剪枝；否则放置 Q 并设置三组标记。
  4. 递归处理下一行，返回后撤销棋盘和全部标记。
  5. row == n 时复制棋盘到答案。

n = 1 时直接得到一个布局；n = 2 或 n = 3 时所有分支都会遇到冲突，答案自然为空，不需要特殊处理。

代码实现

class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];

        for (char[] row : board) {
            Arrays.fill(row, '.');
        }

        List<List<String>> answer = new ArrayList<>();

        dfs(0, board, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], answer);

        return answer;
    }

    private void dfs(
            int row,
            char[][] board,
            boolean[] columns,
            boolean[] diagonals,
            boolean[] antiDiagonals,
            List<List<String>> answer) {
        int n = board.length;

        if (row == n) {
            List<String> solution = new ArrayList<>(n);

            for (char[] line : board) {
                solution.add(new String(line));
            }

            answer.add(solution);

            return;
        }

        for (int col = 0; col < n; col++) {
            // 行减列可能为负，平移后作为同一主对角线的编号。
            int diagonal = row - col + n - 1;
            int antiDiagonal = row + col;

            if (columns[col] || diagonals[diagonal] || antiDiagonals[antiDiagonal]) {
                continue;
            }

            board[row][col] = 'Q';
            columns[col] = true;
            diagonals[diagonal] = true;
            antiDiagonals[antiDiagonal] = true;

            dfs(row + 1, board, columns, diagonals, antiDiagonals, answer);

            // 递归结束后同时撤销棋盘与三类占用，恢复本行选择前的状态。
            board[row][col] = '.';
            columns[col] = false;
            diagonals[diagonal] = false;
            antiDiagonals[antiDiagonal] = false;
        }
    }
}

func solveNQueens(n int) [][]string {
    board := make([][]byte, n)
    for row := range board {
        board[row] = make([]byte, n)
        for col := range board[row] {
            board[row][col] = '.'
        }
    }

    answer := make([][]string, 0)
    columns := make([]bool, n)
    diagonals := make([]bool, 2*n-1)
    antiDiagonals := make([]bool, 2*n-1)

    var dfs func(int)
    dfs = func(row int) {
        if row == n {
            solution := make([]string, n)
            for i := range board {
                solution[i] = string(board[i])
            }
            answer = append(answer, solution)
            return
        }

        for col := 0; col < n; col++ {
            // 行减列可能为负，平移后作为同一主对角线的编号。
            diagonal := row - col + n - 1
            antiDiagonal := row + col
            if columns[col] || diagonals[diagonal] || antiDiagonals[antiDiagonal] {
                continue
            }

            board[row][col] = 'Q'
            columns[col] = true
            diagonals[diagonal] = true
            antiDiagonals[antiDiagonal] = true

            dfs(row + 1)

            board[row][col] = '.'
            // 棋盘已恢复，三类占用也要一起撤销，才能尝试下一列。
            columns[col] = false
            diagonals[diagonal] = false
            antiDiagonals[antiDiagonal] = false
        }
    }

    dfs(0)
    return answer
}

复杂度分析

  • 时间复杂度：上界为 $O(n \cdot n! + S \cdot n^2)$，其中 $S$ 是解的数量。列不能重复，搜索节点数受列排列数量限制；每个节点仍扫描 n 列，每个完整布局还需复制 n² 个字符。
  • 空间复杂度：$O(n^2)$，棋盘占主要空间，标记数组和递归深度为 $O(n)$；返回结果不计入额外空间。

关键点总结

[!green]

  • 逐行放置保证行不冲突，列与两类对角线标记负责剩下的约束。
  • 标记始终与当前棋盘一致，放置和撤销必须成对进行。
  • 找到的是全部布局，收集一个答案后仍须回溯继续搜索。

易错点总结

[!yellow]

  • 对角线标记长度为 2n-1，且 row-col 必须平移 n-1，否则可能越界。
  • 必须在 row == n 时记录，此时最后一行已经放完。
  • 不能把可变棋盘直接加入答案；后续撤销会改变它，必须保存字符串快照。

相似题目

题目 难度 关联与区别
52. N 皇后 II 困难 搜索与约束相同，原题只计数，本题要保存每个棋盘布局。
37. 解数独 困难 同样回溯填棋盘并维护占用约束，本题按列和对角线剪枝。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/89520914
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！