51 N 皇后

一、题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

![](/leetcode/assets/51.N 皇后.png)

二、题解

方法一：回溯 + 布尔数组

思路：使用回溯算法逐行放置皇后，并通过布尔数组快速判断列和两条对角线是否已经存在皇后。

1. 核心思路

由于任意两个皇后都不能位于同一行，所以可以规定：

每一行只放置一个皇后。

从第 0 行开始，依次枚举当前行的每一列。

如果当前位置所在的列、主对角线和副对角线都没有皇后，就可以在这里放置皇后，然后继续处理下一行。

核心思想是：

  • 一行只放置一个皇后，因此不需要额外判断行冲突；
  • 使用布尔数组记录已经被皇后占用的列；
  • 使用两个布尔数组记录已经被占用的两类对角线；
  • 当前选择无法得到完整答案时，撤销选择并尝试其他位置。

对于坐标为 (row, col) 的位置：

主对角线编号：row - col + n - 1
副对角线编号：row + col

同一条主对角线上的位置，row - col 相等。

例如：

(0, 0)、(1, 1)、(2, 2)

它们的 row - col 都等于 0。

因为 row - col 可能是负数，所以加上 n - 1，将编号转换为非负数。

同一条副对角线上的位置，row + col 相等。

例如：

(0, 2)、(1, 1)、(2, 0)

它们的 row + col 都等于 2。

2. 具体步骤

  1. 创建一个 n × n 的棋盘，并将所有位置初始化为 '.'。
  2. 创建三个布尔数组：
    • columns：记录某一列是否已经存在皇后；
    • diagonal1：记录主对角线是否已经存在皇后；
    • diagonal2：记录副对角线是否已经存在皇后。
  3. 从第 0 行开始进行回溯。
  4. 枚举当前行的每一列，计算当前位置对应的两条对角线编号。
  5. 如果当前列或对角线已经存在皇后，则跳过当前位置。
  6. 如果当前位置合法，则放置皇后，并标记对应的列和对角线。
  7. 递归处理下一行。
  8. 递归返回后，撤销皇后以及对应的标记。
  9. 当 row == n 时，说明所有行都成功放置了皇后，记录当前棋盘。

3. 关键逻辑

int d1 = row - col + n - 1;
int d2 = row + col;

// 当前列、主对角线或副对角线已经有皇后
if (columns[col] || diagonal1[d1] || diagonal2[d2]) {
    continue;
}

解释：

  • columns[col] 为 true，表示第 col 列已经存在皇后；
  • diagonal1[d1] 为 true，表示当前位置所在的主对角线已经存在皇后；
  • diagonal2[d2] 为 true，表示当前位置所在的副对角线已经存在皇后；
  • 只要其中任意一个位置已经被占用，当前位置就不能放置皇后。

放置皇后：

board[row][col] = 'Q';
columns[col] = true;
diagonal1[d1] = true;
diagonal2[d2] = true;

递归处理下一行：

backtrack(row + 1);

递归结束后撤销选择：

board[row][col] = '.';
columns[col] = false;
diagonal1[d1] = false;
diagonal2[d2] = false;

这就是回溯算法中的：

做出选择 → 递归搜索 → 撤销选择

4. 代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {

    // 保存所有合法方案
    private List<List<String>> result;

    // 棋盘
    private char[][] board;

    // columns[col] 表示第 col 列是否已经存在皇后
    private boolean[] columns;

    // 主对角线：row - col + n - 1
    private boolean[] diagonal1;

    // 副对角线：row + col
    private boolean[] diagonal2;

    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.result = new ArrayList<>();
        this.board = new char[n][n];

        // 一共有 n 列
        this.columns = new boolean[n];

        // 两类对角线的编号范围都是 0 ~ 2n - 2
        this.diagonal1 = new boolean[2 * n - 1];
        this.diagonal2 = new boolean[2 * n - 1];

        // 初始化棋盘
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }

        // 从第 0 行开始放置皇后
        backtrack(0);

        return result;
    }

    /**
     * 尝试在第 row 行放置皇后
     */
    private void backtrack(int row) {
        // 所有行都成功放置了皇后
        if (row == n) {
            result.add(buildBoard());
            return;
        }

        // 枚举当前行的每一列
        for (int col = 0; col < n; col++) {
            // 计算当前位置对应的两条对角线编号
            int d1 = row - col + n - 1;
            int d2 = row + col;

            // 当前列或对角线已经存在皇后，不能放置
            if (columns[col] || diagonal1[d1] || diagonal2[d2]) {
                continue;
            }

            // 做出选择：在当前位置放置皇后
            board[row][col] = 'Q';
            columns[col] = true;
            diagonal1[d1] = true;
            diagonal2[d2] = true;

            // 递归处理下一行
            backtrack(row + 1);

            // 撤销选择
            board[row][col] = '.';
            columns[col] = false;
            diagonal1[d1] = false;
            diagonal2[d2] = false;
        }
    }

    /**
     * 将当前棋盘转换为题目要求的 List<String>
     */
    private List<String> buildBoard() {
        List<String> solution = new ArrayList<>();

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

        return solution;
    }
}

5. 复杂度分析

时间复杂度：O(n!)O(n!)

说明：

第一行最多可以选择 n 个位置，第二行最多可以选择 n - 1 个位置，后面的行可选择的位置会继续减少。

在不考虑对角线剪枝的情况下，搜索规模接近：

n × (n - 1) × (n - 2) × ... × 1

因此时间复杂度可以近似看作 O(n!)O(n!)。

生成每个合法棋盘还需要 O(n2)O(n^2) 的时间。

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

说明：

  • 棋盘需要 O(n2)O(n^2) 的空间；
  • 三个标记数组需要 O(n)O(n) 的空间；
  • 递归调用栈最大深度为 O(n)O(n)。

因此，不计算最终返回结果所占空间时，总空间复杂度为 O(n2)O(n^2)。

方法二：回溯 + 位运算

思路：使用整数的二进制位记录已经被占用的列和对角线，从而快速计算当前行所有可以放置皇后的位置。

1. 核心思路

方法一使用三个布尔数组记录列和对角线的占用情况。

方法二使用整数的二进制位进行记录。

例如，当 n = 4 时：

0001：表示第 0 列被占用
0100：表示第 2 列被占用
0101：表示第 0 列和第 2 列被占用

定义三个整数：

columns：已经被皇后占用的列
leftDiagonals：当前行被左斜对角线攻击的位置
rightDiagonals：当前行被右斜对角线攻击的位置

将三个整数进行按位或运算：

columns | leftDiagonals | rightDiagonals

得到当前行所有不能放置皇后的位置。

再对结果取反，就可以得到可以放置皇后的位置：

~(columns | leftDiagonals | rightDiagonals)

由于只需要考虑最低的 n 位，因此还需要与 limit 进行按位与：

int available = limit
        & ~(columns | leftDiagonals | rightDiagonals);

其中：

limit = (1 << n) - 1;

当 n = 4 时：

1 << 4        = 10000
(1 << 4) - 1  = 01111

因此 limit 的最低 n 位全部为 1。

2. 具体步骤

  1. 使用 limit = (1 << n) - 1 表示棋盘中的所有列。
  2. 使用 columns 记录已经被占用的列。
  3. 使用 leftDiagonals 和 rightDiagonals 记录当前行被两类对角线攻击的位置。
  4. 通过按位或运算得到当前行所有不能放置皇后的位置。
  5. 对结果取反，并使用 limit 保留最低的 n 位，得到所有可选位置。
  6. 使用 available & -available 取出最右侧的一个可选位置。
  7. 将对应位置设置为皇后，并递归处理下一行。
  8. 进入下一行时，对两个对角线状态分别进行左移和右移。
  9. 递归结束后，将棋盘当前位置恢复为 '.'。

3. 关键逻辑

计算当前行所有可以放置皇后的位置：

int available = limit
        & ~(columns | leftDiagonals | rightDiagonals);

解释：

  • columns | leftDiagonals | rightDiagonals 表示所有不能放置皇后的位置；
  • 对结果取反后，二进制位为 1 的位置就是可以放置皇后的位置；
  • 与 limit 进行按位与，只保留最低的 n 位。

取出最右侧的一个 1：

int position = available & -available;

例如：

available = 10100
-position 对应的补码运算结果
available & -available = 00100

因此可以取出最右侧的可选位置。

删除已经处理的最低位 1：

available &= available - 1;

进入下一行时更新对角线：

((leftDiagonals | position) << 1) & limit
(rightDiagonals | position) >> 1

解释：

  • 左斜对角线对下一行的攻击位置需要左移一位；
  • 右斜对角线对下一行的攻击位置需要右移一位；
  • & limit 用来保证只保留棋盘范围内的最低 n 位。

4. 代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {

    // 保存所有合法方案
    private List<List<String>> result;

    // 棋盘
    private char[][] board;

    // 低 n 位全部为 1
    private int limit;

    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.result = new ArrayList<>();
        this.board = new char[n][n];

        // 例如 n = 4 时，limit = 1111
        this.limit = (1 << n) - 1;

        // 初始化棋盘
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }

        // 从第 0 行开始搜索
        dfs(0, 0, 0, 0);

        return result;
    }

    /**
     * @param row            当前处理的行
     * @param columns        已经被占用的列
     * @param leftDiagonals  当前行被左斜对角线攻击的位置
     * @param rightDiagonals 当前行被右斜对角线攻击的位置
     */
    private void dfs(
            int row,
            int columns,
            int leftDiagonals,
            int rightDiagonals) {

        // 所有行都成功放置了皇后
        if (row == n) {
            result.add(buildBoard());
            return;
        }

        // 计算当前行所有可以放置皇后的位置
        int available = limit
                & ~(columns | leftDiagonals | rightDiagonals);

        // 依次处理每一个可选位置
        while (available != 0) {
            // 取出 available 中最右侧的 1
            int position = available & -available;

            // 删除已经取出的最低位 1
            available &= available - 1;

            // 根据 position 得到对应的列下标
            int col = Integer.numberOfTrailingZeros(position);

            // 做出选择
            board[row][col] = 'Q';

            // 递归处理下一行
            dfs(
                row + 1,
                columns | position,
                ((leftDiagonals | position) << 1) & limit,
                (rightDiagonals | position) >> 1
            );

            // 撤销选择
            board[row][col] = '.';
        }
    }

    /**
     * 将当前棋盘转换为题目要求的 List<String>
     */
    private List<String> buildBoard() {
        List<String> solution = new ArrayList<>();

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

        return solution;
    }
}

5. 复杂度分析

时间复杂度：O(n!)O(n!)

说明：

位运算优化了判断当前位置是否合法的过程，但需要搜索的状态数量并没有发生本质变化。

因此，回溯搜索的时间复杂度仍然可以近似看作 O(n!)O(n!)。

生成每个合法棋盘还需要 O(n2)O(n^2) 的时间。

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

说明：

  • 棋盘需要 O(n2)O(n^2) 的空间；
  • 递归调用栈最大深度为 O(n)O(n)；
  • 列和对角线状态使用几个整数保存，只需要 O(1)O(1) 的额外空间。

因此，不计算最终返回结果所占空间时，总空间复杂度为 O(n2)O(n^2)。

评论