51. N 皇后

鲁迅曾说过，有一段时间没有刷二哥的 LeetCode 刷题笔记了，心里痒痒的，今

天我们开始刷 N 皇后吧，这道题可有意思了，比天天背八股来得开心多了。

题意

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

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

互攻击。

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

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

后和空位。

难度

困难

示例

示例 1：

051.N 皇后-20241107143433.png

输入：n = 4

输出：[

[".Q..",

"...Q",

"Q...",

"..Q."],

["..Q.",

"Q...",

"...Q",

".Q.."]]

解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1

输出：[["Q"]]

分析

运用递归+回溯的知，我其 足

要

定

一

心

信

（

目

道

出

解

就

力

之

灰

吹

不

以 ?

N 皇后是一道非常经典的递归+回溯题目，但是这并不意味着它就非常的难，相反，合理

们其可

。实可 以 “不 费吹 灰 之 力 ”就 解 出 这道 题目 （ 信 心 一 定 要 足 ? ） 。

）

我们知道，一个 皇后 能够攻击她所在的 行、列、斜线上的棋子，那我们就直接从第一行

开始，逐行放置皇后，然后判断当前位置是否合法，如果合法，我们就继续放置下一个皇

后，如果不合法，我们就回溯到上一步，重新放置皇后。

非常暴力，但很容易上手。

class Solution {

// 解决 N 皇后问题

public List<List<String>> solveNQueens(int n) {

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

// 初始化棋盘

char[][] board = new char[n][n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

board[i][j] = '.';

}

}

// 开始递归查找所有解

backtrack(solutions, board, 0, n);

return solutions;

}

// 回溯方法

private void backtrack(List<List<String>> solutions, char[][] board, int row,

int n) {

// 如果已成功放置完所有皇后，将当前棋盘方案加入 solutions

if (row == n) {

solutions.add(construct(board));

return;

}

// 尝试在当前行的每一列放置皇后

for (int col = 0; col < n; col++) {

// 检查当前位置是否安全

 if (isValid(board, row, col, n)) {

// 放置皇后

board[row][col] = 'Q';

// 递归处理下一行

backtrack(solutions, board, row + 1, n);

// 回溯，撤销当前放置

board[row][col] = '.';

}

}

}

// 检查在 (row, col) 位置放置皇后是否安全

private boolean isValid(char[][] board, int row, int col, int n) {

// 检查列上是否有皇后

for (int i = 0; i < row; i++) {

if (board[i][col] == 'Q') {

return false;

}

}

// 检查左上方对角线上是否有皇后

for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {

if (board[i][j] == 'Q') {

return false;

}

}

// 检查右上方对角线上是否有皇后

for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {

if (board[i][j] == 'Q') {

return false;

}

}

return true;

}

// 将当前棋盘状态转换为字符串列表

private List<String> construct(char[][] board) {

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

for (int i = 0; i < board.length; i++) {

result.add(new String(board[i]));

}

return result;

}

public static void main(String[] args) {

Solution solution = new Solution();

System.out.println(solution.solveNQueens(4));

 }

}

第一步，初始化棋盘，用一个二维数组 board 来表示棋盘，初始化为全是 .。

char[][] board = new char[n][n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

board[i][j] = '.';

}

}

第二步，利用回溯方法 backtrack 递归查找所有解，其中 row 表示当前行，n 表示总行

数。

private void backtrack(List<List<String>> solutions, char[][] board, int row, int

n) {

// 如果已成功放置完所有皇后，将当前棋盘方案加入 solutions

if (row == n) {

solutions.add(construct(board));

return;

}

// 尝试在当前行的每一列放置皇后

for (int col = 0; col < n; col++) {

// 检查当前位置是否安全

if (isValid(board, row, col, n)) {

// 放置皇后

board[row][col] = 'Q';

// 递归处理下一行

backtrack(solutions, board, row + 1, n);

// 回溯，撤销当前放置

board[row][col] = '.';

}

}

}

• 每次递归表示在当前行放置一个皇后。递归深度等于 n 时，表示所有皇后都成功放

置，保存当前棋盘方案。

• 每放置一个皇后，都要检查当前位置是否安全，即是否满足不在同一列、同一左上方

对角线、同一右上方对角线上有皇后。

• 如果当前位置安全，放置皇后（将该位置标记为 Q），递归处理下一行，然后回溯撤

销当前放置 board[row][col] = '.'。

可能有些球友不理解为什么调用 backtrack() 方法后要 board[row][col] = '.'，debug 一次

就很明白了。

比如说 N 等于 4 的时候，我们从第一行的第一个位置开始放置皇后，满足条件，我们递

归处理第二行，发现第二行的第三个位置满足条件，我们递归处理第三行，结果发现没有

满足条件的位置。

这个时候怎么办呢？

就要撤销第二步的选择，继续尝试第二行的第四个位置，对吧？

051.N 皇后-20241107153120.png

依次继续找，找到第一种方案后，return，撤销当前选择，尝试下一个方案。

051.N 皇后-20241107153925.png

直到找到第二种方案。

051.N 皇后-20241107154328.png

好，我们再来理一下回溯算法的整体框架：

// 回溯算法框架

void backtrack(参数) {

if (满足结束条件) {

记录或输出解;

return;

}

for (选择 : 当前状态的所有选择) {

做出选择;

递归到下一层，继续探索;

撤销选择; // 回溯

}

}

①、确定递归结束的条件。

②、在当前状态在做出选择，递归到下一次，继续探索。

③、发现条件不满足或者所有选择都尝试了，撤销当前选择，回溯到上一个状态，继续尝

试其他选择。（这也是回溯算法的核心）

第三步，检查在 (row, col) 位置放置皇后是否安全。也就是从列（这个大家都能抽象出画

面）、两个对角线（截图大家感受一下）判断。

051.N 皇后-20241107155138.png

051.N 皇后-20241107155159.png

private boolean isValid(char[][] board, int row, int col, int n) {

// 检查列上是否有皇后

for (int i = 0; i < row; i++) {

if (board[i][col] == 'Q') {

return false;

}

}

// 检查左上方对角线上是否有皇后

for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {

if (board[i][j] == 'Q') {

return false;

}

}

// 检查右上方对角线上是否有皇后

for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {

if (board[i][j] == 'Q') {

return false;

}

}

return true;

}

最后，就是需要将二维数组转换为字符串列表。

private List<String> construct(char[][] board) {

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

for (int i = 0; i < board.length; i++) {

result.add(new String(board[i]));

}

return result;

}

整体的题解效率还不错。

051.N 皇后-20241107155403.png

总结

整体上，这道题还是考察的回溯算法，利用递归和边界条件判断，要能理解和记住回溯算

法的整体框架，这样就只剩下代码上的实现了。

力扣链接：https://leetcode.cn/problems/n-queens/