跳到主要内容

LeetCode 51. N 皇后

本节目标

按行放置皇后，并增量维护列、主对角线与副对角线约束。

这道题使用约束型回溯中的集合约束：按行放置皇后，列、主对角线和副对角线任一被占用时，都不再深入该分支。

查看 LeetCode 原题

题意与约束​

在 n × n 棋盘上放置 n 个皇后，要求任意两个皇后不在同一行、同一列或同一条对角线上，返回所有棋盘布局。每个布局用 Q 与 . 表示。

朴素思路与瓶颈​

若从每个格子任意选择位置，再到叶子检查冲突，候选数量接近 n^n，并且会反复产生同一行多个皇后的明显非法状态。即使规定每行一个皇后，仍需要及时判断列和对角线冲突。

三类占用状态​

递归参数 row 表示当前要摆放哪一行，因此行冲突天然不存在。对候选 (row, column)，维护：

  • columns：已经放置皇后的列；
  • diagonals：主对角线编号 row - column；
  • antiDiagonals：副对角线编号 row + column。

三个编号相同就代表两格在同一条相应对角线上。选择一个位置时，同时写入棋盘并登记三类集合；递归返回后，按相反顺序清除棋盘和集合。row == n 时每行恰有一个皇后且所有约束都成立，复制当前棋盘即可。

正确性依据​

归纳地看，进入第 row 层时，之前每一行恰有一个皇后，三类集合精确记录它们占用的列和对角线。算法仅选择不在这些集合中的列，因此新增皇后不与已有皇后攻击。完成状态有 n 行皇后且不冲突，必是合法解。反过来，任一合法布局在每一行的皇后列均不会触发集合冲突，循环会依次选择这些列，因此不会漏解。

代码实现​

C++17
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<string>> boards;
    unordered_set<int> columns;
    unordered_set<int> diagonals;
    unordered_set<int> antiDiagonals;

    void backtrack(vector<string>& board, int row) {
        const int size = static_cast<int>(board.size());
        if (row == size) {
            boards.push_back(board);
            return;
        }

        for (int column = 0; column < size; column++) {
            const int diagonal = row - column;
            const int antiDiagonal = row + column;
            if (columns.find(column) != columns.end() ||
                diagonals.find(diagonal) != diagonals.end() ||
                antiDiagonals.find(antiDiagonal) != antiDiagonals.end()) {
                continue;
            }

            columns.insert(column);
            diagonals.insert(diagonal);
            antiDiagonals.insert(antiDiagonal);
            board[row][column] = 'Q';
            backtrack(board, row + 1);
            board[row][column] = '.';
            antiDiagonals.erase(antiDiagonal);
            diagonals.erase(diagonal);
            columns.erase(column);
        }
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        boards.clear();
        columns.clear();
        diagonals.clear();
        antiDiagonals.clear();
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0);
        return boards;
    }
};

复杂度分析​

搜索会尝试受约束的行列排列，最坏枚举规模为 O(n!)；每个完整布局复制 n 行、每行 n 个字符，输出复制成本为 O(R · n^2)，其中 R 是解的数量。集合查询和更新平均为 O(1)；递归栈、棋盘与三类集合的额外空间为 O(n^2)。

易错点​

  • 把 row - column 当作数组下标却没有处理负数；使用集合可直接保存负编号。
  • 只检查列，遗漏两类对角线冲突。
  • 回溯后只把棋盘恢复成 .，没有从集合删除占用，导致错误剪枝。
  • 用 solve 替代题目要求的 solveNQueens，破坏平台接口。

模式迁移​

数独、图着色和安排问题都可把“已经不可再选”的信息变成集合、位集或计数器。先让一个维度按固定顺序推进，再把其余冲突维护为可增删状态，是将全局约束转成局部剪枝的常用方法。