【LeetCode热题100道笔记】N 皇后

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：n = 1
输出：[[“Q”]]

提示：

• 1 <= n <= 9

思考

n 皇后问题的核心是在 n×n 棋盘上放置 n 个皇后，确保任意两个皇后不共行、不共列、不共斜线。由于需探索所有合法方案，且探索过程中需“试错回退”，因此采用 回溯法 求解，关键优化点如下：

1. 按行递归：每一行仅需放置 1 个皇后（避免共行冲突），递归时按“行”推进（从第 0 行到第 n-1 行），减少无效探索。
2. 高效冲突检测：用 3 个布尔数组快速判断当前位置是否冲突：
   • cols[col]：标记第 col 列是否已有皇后（避免共列）；
   • diag1[d1]：标记“左上→右下”方向的斜线是否已有皇后（同一斜线的 row - col 值相等，d1 = row - col + n -1 是为了将负索引转为正索引）；
   • diag2[d2]：标记“右上→左下”方向的斜线是否已有皇后（同一斜线的 row + col 值相等，d2 = row + col）。

斜线冲突索引计算

为了用数组高效标记斜线冲突，需将“斜线”映射为唯一的数组索引，具体逻辑如下：

例：n=4 时，(0,0) 的 d1=0-0+3=3、d2=0；(1,1) 的 d1=1-1+3=3、d2=2，二者 d1 不同，不共“左上→右下”斜线。

算法过程

1. 初始化

• result：存储所有合法解决方案（每个方案是 ["Q..", "...Q"] 格式的字符串数组）；
• board：n×n 棋盘，初始值为 .（空位），用于临时存储当前放置方案；
• cols：长度为 n 的布尔数组，标记列冲突；
• diag1/diag2：长度为 2n-1 的布尔数组，标记两个方向的斜线冲突。

2. 递归回溯（dfs(row)）

递归函数作用：处理第 row 行的皇后放置，探索所有合法列位置。

（1）终止条件

当 row === n 时，说明已成功在 n 行放置 n 个皇后，将当前棋盘转为字符串数组（board.map(item => item.join(''))），加入 result 并返回。

（2）列遍历与冲突判断

遍历第 row 行的每一列 col（0 ≤ col < n），计算当前位置的斜线索引 d1 和 d2，判断是否冲突：

• 若 cols[col]、diag1[d1]、diag2[d2] 均为 false，说明当前位置合法，可放置皇后。

（3）放置皇后与递归

• 标记状态：将 board[row][col] 设为 Q，并将 cols[col]、diag1[d1]、diag2[d2] 设为 true（标记冲突）；
• 递归下一行：调用 dfs(row + 1)，探索下一行的皇后放置；
• 回溯还原：递归返回后，将 board[row][col] 还原为 .，并将冲突标记设为 false（撤销当前选择，探索其他列）。

3. 启动与返回

调用 dfs(0) 从第 0 行开始递归，最终返回 result 即为所有合法方案。

复杂度分析

• 时间复杂度：$O(n!)$
  第 0 行有 n 种列选择，第 1 行有 n-1 种（排除已用列和斜线），第 2 行有 n-2 种，……，第 n-1 行有 1 种，总探索次数为 $n\times (n-1)\times (n-2)\times \dots \times 1=n!$；每次递归终止时，转换棋盘格式需 $O(n^2)$ 时间（但 $n!$ 是主导项，可忽略 $n^2$）。

• 空间复杂度：$O(n^2)$

  • 棋盘 board 占用 $O(n^2)$ 空间；
  • 递归栈深度为 $n$（最多递归 n 层），冲突数组 cols/diag1/diag2 占用 $O(n)$ 空间（diag1/diag2 长度为 $2n-1$，属于 $O(n)$）；
  • 总空间由棋盘主导，为 $O(n^2)$。

代码

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const result = [];
    const board = Array.from({length: n}, () => Array(n).fill('.'));
    const cols = Array(n).fill(false);
    const diag1 = new Array(2 * n - 1).fill(false);
    const diag2 = new Array(2 * n - 1).fill(false);

    const dfs = function(row) {
        if (row === n) {
            result.push(board.map(item => item.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            const d1 = row - col + n - 1;
            const d2 = row + col; 
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                board[row][col] = 'Q';
                cols[col] = true;
                diag1[d1] = true;
                diag2[d2] = true;

                dfs(row + 1);

                board[row][col] = '.';
                cols[col] = false;
                diag1[d1] = false;
                diag2[d2] = false;
            }
        }      


    };

    dfs(0);
  
    return result;
};