题目

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 皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列、行程问题之后，遇到这种二维矩阵还会有点不知所措。

首先来看一下皇后们的约束条件：

不能同行
不能同列
不能同斜线

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。

下面我用一个3 * 3 的棋牌，将搜索过程抽象为一颗树，如图：

从图中，可以看出，二维矩阵中矩阵的高就是这颗树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

那么我们用皇后们的约束条件，来回溯搜索这颗树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

回溯三部曲

按照我总结的如下回溯模板，我们来依次分析：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

1、递归函数参数

我依然是定义全局变量二维数组 result 来记录最终结果。

参数 n 是棋牌的大小，然后用 row 来记录当前遍历到棋盘的第几层了。
代码如下：

int n = 0;
char[][] chessboard = null; // 棋盘
List<List<String>> result = new ArrayList<>(); // 存储结果
void backTracking(int row)

2、递归终止条件

在如下树形结构中：

可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。

代码如下：

if (row == n) {
    // row 是从 0 开始的，因此 row==n 时，说明棋盘的每一行已经遍历完成，此时棋盘的状态即为一种解
    result.add(Array2List(chessboard));
    return;
}

3、单层搜索的逻辑

递归深度就是 row 控制棋盘的行，每一层里 for 循环的 col 控制棋盘的列，一行一列，确定了放置皇后的位置。

每次都是要从新的一行的起始位置开始搜，所以都是从 0 开始。

代码如下：

for (int col = 0; col < n; ++col) {
    if (isValid(row, col)) {        // 若该坐标合法
        chessboard[row][col] = 'Q'; // 放入皇后
        backTracking(row + 1);      // 遍历下一行 row+1
        chessboard[row][col] = '.'; // 回溯，撤销皇后
    }
}

验证棋盘是否合法

按照如下标准去重：

不能同行
不能同列
不能同斜线（45度和135度角）

代码如下：

// 检查该坐标是否可以放入皇后
public boolean isValid(int row, int col) {
    // 检查列
    for (int i = 0; i < row; ++i) { // 相当于剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查45度对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查135度对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？

因为在单层搜索的过程中，每一层递归，只会选 for 循环（也就是同一行）里的一个元素，所以不用去重了。

那么按照这个模板就不难写出答案了。

总结

本题是我们解决棋盘问题的第一道题目。

如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。

这里我明确给出了棋盘的宽度就是 for 循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

大家可以再仔细体会体会！

答案

Java

class Solution {
    int n = 0;
    char[][] chessboard = null; // 棋盘
    List<List<String>> result = new ArrayList<>(); // 存储结果的 list
    public List<List<String>> solveNQueens(int n) {
        // 写入全局参数，避免函数参数过多影响可读性
        this.n = n;
        // 初始化棋盘
        chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        // 棋盘的宽度就是 for 循环的长度，递归的深度就是棋盘的高度，从第一行开始遍历
        backTracking(0);
        return result;
    }
    public void backTracking(int row) {
        // 终止条件
        if (row == n) {
            // row 是从 0 开始的，因此 row==n 时，说明棋盘的每一行已经遍历完成，此时棋盘的状态即为一种解
            result.add(Array2List(chessboard));
            return;
        }
        // 循环遍历第 row 行的每一个空格，尝试放入皇后
        for (int col = 0; col < n; ++col) {
            // 若该坐标合法
            if (isValid(row, col)) {
                // 放入皇后
                chessboard[row][col] = 'Q';
                // 遍历下一行 row+1
                backTracking(row + 1);
                // 回溯
                chessboard[row][col] = '.';
            }
        }
    }
    // 检查该坐标是否可以放入皇后
    public boolean isValid(int row, int col) {
        // 检查列
        for (int i = 0; i < row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
    // 将棋盘二维数组转换为 List，因为题目要求的数据格式如此
    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}

REF

https://programmercarl.com/0051.N皇后.html
https://leetcode-cn.com/problems/n-queens/

算法总纲

51. N 皇后

题目

思路

回溯三部曲

1、递归函数参数

2、递归终止条件

3、单层搜索的逻辑

验证棋盘是否合法

总结

答案

Java

REF