原文链接: https://leetcode-cn.com/problems/n-queens

英文原文

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

 

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

 

Constraints:

• 1 <= n <= 9

中文题目

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 皇后问题很多时候作为例题出现在教科书中，可以当做理解回溯算法的例题进行学习；
• 对于回溯算法还比较陌生的朋友，可以参考我的题解 《回溯算法入门级详解 + 练习（持续更新）》。

---

思路分析：以 $4$ 皇后问题为例，它的「搜索」过程如下。大家可以在纸上模拟下面这个过程：

<,,,,,,,,,,,,,,,,,,,,,,,,,,,,,>

（早期写的题解配色较差，请大家谅解。）

理解树形结构

先尝试画出递归树，以 $4$ 皇后问题为例，画出的递归树如下：

搜索的过程蕴含了 剪枝 的思想。「剪枝」的依据是：题目中给出的 「N 皇后」 的摆放规则：1、不在同一行；2、不在同一列；3、不在同一主对角线方向上；4、不在同一副对角线方向上。

小技巧：记住已经摆放的皇后的位置

这里记住已经摆放的位置不能像 Flood Fill 一样，简单地使用 visited 布尔数组。放置的规则是：一行一行考虑皇后可以放置在哪一个位置上，某一行在考虑某一列是否可以放置皇后的时候，需要根据前面已经放置的皇后的位置。

由于是一行一行考虑放置皇后，摆放的这些皇后肯定不在同一行，为了避免它们在同一列，需要一个长度为 $N$ 的布尔数组 cols，已经放置的皇后占据的列，就需要在对应的列的位置标注为 True。

考虑对角线（找规律）

下面我们研究一下主对角线或者副对角线上的元素有什么特性。在每一个单元格里写下行和列的 下标。

为了保证至少两个皇后不同时出现在 同一主对角线方向 或者 同一副对角线方向。检查策略是，只要「检测」到新摆放的「皇后」与已经摆放好的「皇后」冲突，就尝试摆放同一行的下一个位置，到行尾还不能放置皇后，就退回到上一行。

可以像全排列 used 数组那样，再为 「主对角线（Main diagonal）」 和 「副对角线（Sub diagonal）」 设置相应的 布尔数组变量，只要排定一个 「皇后」 的位置，就需要占住对应的位置。

编码

我们使用一个 $1$ 到 $4$ 的排列表示一个 $4 \times 4$ 的棋盘，例如：

{:width=”500px”}

得到一个符合要求的全排列以后，生成棋盘的代码就很简单了。

说明：

• 将「行状态」、「主对角线状态」、「副对角线状态」 设置为成员变量，以避免递归方法参数冗长（参考代码 2、参考代码 3 类似看待）。至于是否有必要这样做，以后在项目开发中需要遵守项目文档的规定；
• Java 中 Stack 已经废弃，推荐使用 ArrayDeque，可以查阅文档。

方法：回溯搜索算法（深度优先遍历）

下面虽然给出了 3 版代码，但都只是在如何记住已经摆放的皇后的位置上做文章，代码结构都一样，大家只看不同的部分就可以了。

参考代码 1：

[]
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {

    private int n;
    /**
     * 记录某一列是否放置了皇后
     */
    private boolean[] col;
    /**
     * 记录主对角线上的单元格是否放置了皇后
     */
    private boolean[] main;
    /**
     * 记录了副对角线上的单元格是否放置了皇后
     */
    private boolean[] sub;
    private List<List<String>> res;

    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        // 设置成员变量，减少参数传递，具体作为方法参数还是作为成员变量，请参考团队开发规范
        this.n = n;
        this.col = new boolean[n];
        this.main = new boolean[2 * n - 1];
        this.sub = new boolean[2 * n - 1];
        Deque<Integer> path = new ArrayDeque<>();
        dfs(0, path);
        return res;
    }

    private void dfs(int row, Deque<Integer> path) {
        if (row == n) {
            // 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果
            List<String> board = convert2board(path);
            res.add(board);
            return;
        }

        // 针对下标为 row 的每一列，尝试是否可以放置
        for (int j = 0; j < n; j++) {
            if (!col[j] && !main[row - j + n - 1] && !sub[row + j]) {
                path.addLast(j);
                col[j] = true;
                main[row - j + n - 1] = true;
                sub[row + j] = true;


                dfs(row + 1, path);
                sub[row + j] = false;
                main[row - j + n - 1] = false;
                col[j] = false;
                path.removeLast();
            }
        }
    }

    private List<String> convert2board(Deque<Integer> path) {
        List<String> board = new ArrayList<>();
        for (Integer num : path) {
            StringBuilder row = new StringBuilder();
            row.append(".".repeat(Math.max(0, n)));
            row.replace(num, num + 1, "Q");
            board.add(row.toString());
        }
        return board;
    }
}

参考代码 2：其实已经摆放皇后的列下标、占据了哪一条主对角线、哪一条副对角线也可以使用哈希表来记录。

实际上哈希表底层也是数组，使用哈希表可以不用处理已经占据位置的皇后的主对角线、副对角线的下标偏移问题。

[]
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    private Set<Integer> col;
    private Set<Integer> main;
    private Set<Integer> sub;
    private int n;
    private List<List<String>> res;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        col = new HashSet<>();
        main = new HashSet<>();
        sub = new HashSet<>();

        Deque<Integer> path = new ArrayDeque<>();
        dfs(0, path);
        return res;
    }

    private void dfs(int row, Deque<Integer> path) {
        if (row == n) {
            List<String> board = convert2board(path);
            res.add(board);
            return;
        }

        // 针对每一列，尝试是否可以放置
        for (int i = 0; i < n; i++) {
            if (!col.contains(i) && !main.contains(row - i) && !sub.contains(row + i)) {
                path.addLast(i);
                col.add(i);
                main.add(row - i);
                sub.add(row + i);

                dfs(row + 1, path);

                sub.remove(row + i);
                main.remove(row - i);
                col.remove(i);
                path.removeLast();
            }
        }
    }

    private List<String> convert2board(Deque<Integer> path) {
        List<String> board = new ArrayList<>();
        for (Integer num : path) {
            StringBuilder row = new StringBuilder();
            row.append(".".repeat(Math.max(0, n)));
            row.replace(num, num + 1, "Q");
            board.add(row.toString());
        }
        return board;
    }
}

参考代码 3：搜索问题一般来说复杂度很高，因此在线测评系统的后台测试数据不会很大。因此布尔数组可以只用一个整数来代替（int 或者 long 根据情况决定），int 类型整数等价于一个 $32$ 位布尔数组，long 类型整数等价于一个 $64$ 位布尔数组。

使用一个整数代表一个布尔数组，在比较布尔数组所有的位的值是否相等时，只需要 $O(1)$，并且传递参数、复制也是相对方便的。这样的技巧叫做「状态压缩」，动态规划问题里有一类问题就叫做状态压缩 dp（我学不过来了，以后学会了再向大家介绍，请谅解）。

状态压缩的缺点是：编码得很细心，不容易调试。

「力扣」第 1371 题：每个元音包含偶数次的最长子字符串，是每日一题出现过的状态压缩的经典问题，综合使用了很多算法思想和技巧，感兴趣的朋友可以复习一下。

说明：使用 状态压缩 技巧，可以完成 「力扣」第 52 题：「N皇后 II」。

[]
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {

    private List<List<String>> res;
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        int col = 0;
        int main = 0;
        int sub = 0;
        Deque<Integer> path = new ArrayDeque<>();

        dfs(0, col, main, sub, path);
        return res;
    }

    private void dfs(int row, int col, int sub, int main, Deque<Integer> path) {
        if (row == n) {
            List<String> board = convert2board(path);
            res.add(board);
            return;
        }

        // 针对每一列，尝试是否可以放置
        for (int i = 0; i < n; i++) {
            if (((col >> i) & 1) == 0 
                    && ((main >> (row - i + n - 1)) & 1) == 0 
                    && ((sub >> (row + i)) & 1) == 0) {
                path.addLast(i);
                col ^= (1 << i);
                main ^= (1 << (row - i + n - 1));
                sub ^= (1 << (row + i));

                dfs(row + 1, col, sub, main, path);

                sub ^= (1 << (row + i));
                main ^= (1 << (row - i + n - 1));
                col ^= (1 << i);
                path.removeLast();
            }
        }
    }

    private List<String> convert2board(Deque<Integer> path) {
        List<String> board = new ArrayList<>();
        for (Integer num : path) {
            StringBuilder row = new StringBuilder();
            row.append(".".repeat(Math.max(0, n)));
            row.replace(num, num + 1, "Q");
            board.add(row.toString());
        }
        return board;
    }
}

同类问题

• 37. 解数独
• 679. 24 点游戏
• 529. 扫雷游戏
• 488. 祖玛游戏

参考资料

• liuyubobobo 老师在慕课网上开设的课程《玩转算法面试》代码仓库；
• 《剑指 Offer（第 2 版）》面试题 38 ：字符串的排列，相关题目 2。

一个回溯算法可视化的小项目

通过可视化帮助理解回溯算法的思想。写 Java 的朋友可以看看，这是我写的一个练习的项目，学习的价值不大，不用点赞。

• GitHub 地址：Backtracking-Visualization

统计信息

通过次数	提交次数	AC比率
165769	224763	73.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
N皇后 II	困难
网格照明	困难