问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击
给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案

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

示例 1：
leetcode-51：N皇后 - 图1
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

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

提示：
皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退

思路

都知道n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列问题之后，遇到这种二位矩阵还会有点不知所措

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

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

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树
下面我用一个3 * 3 的棋牌，将搜索过程抽象为一颗树，如图：
leetcode-51：N皇后 - 图2
51.N皇后
从图中，可以看出，二维矩阵中矩阵的高就是这颗树的高度，矩阵的宽就是树型结构中每一个节点的宽度
那么我们用皇后们的约束条件，来回溯搜索这颗树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了

回溯三部曲

回溯模板

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

  • 递归函数参数

    • 定义全局变量二维数组result来记录最终结果
    • 参数n是棋牌的大小，然后用row来记录当前遍历到棋盘的第几层了
      1. List<List<String>> result = new ArrayList<>();
      2. public void backtracking(int n, int row, char[][] chessboard) {

  • 递归终止条件

在如下树形结构中：leetcode-51：N皇后 - 图3
可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了

  1. if (row == n) {
  2.     result.add(ArraytoList(chessboard));
  3.     return;
  4. }
  6. public List ArraytoList(char[][] chessboard) {
  7.         List<String> list = new ArrayList<>();
  9.         for (char[] c : chessboard) {
  10.             list.add(String.copyValueOf(c)); //返回指定数组中表示该字符序列的字符串
  11.         }
  12.         return list;
  13.     }

  • 单层搜索的逻辑

    • 递归深度就是**row**控制棋盘的行，每一层里**for**循环的**col**控制棋盘的列，一行一列，确定了放置皇后的位置
      1. for (int col = 0; col < n; col++) {
      2. if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
      3.    chessboard[row][col] = 'Q'; // 放置皇后
      4.    backtracking(n, row + 1, chessboard);
      5.    chessboard[row][col] = '.'; // 回溯，撤销皇后
      6. }
      7. }

  • 验证棋牌是否合法

    • 按照如下标准去重：

      • 不能同行
      • 不能同列
      • 不能同斜线 （45度和135度角）
        1. public boolean isValid(int row, int col, char[][] chessboard, int n) {
        2. // 检查列
        3. for (int i = 0; i < n; i++) { // 这是一个剪枝
        4. if (chessboard[i][col] == 'Q') {
        5.     return false;
        6. }
        7. }
        8. // 检查 45度角是否有皇后
        9. for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        10. if (chessboard[i][j] == 'Q') {
        11.     return false;
        12. }
        13. }
        14. // 检查 135度角是否有皇后
        15. for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        16. if (chessboard[i][j] == 'Q') {
        17.     return false;
        18. }
        19. }
        20. return true;
        21. }
        那么为什么没有在同行进行检查呢？
        因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重 ```java class Solution { List> result = new ArrayList<>();

      public List> solveNQueens(int n) { char[][] chessboard = new char[n][n]; for (char[] c : chessboard) {

      1.    Arrays.fill(c, '.');

      } backTrack(n, 0, chessboard); return result; }

public void backTrack(int n, int row, char[][] chessboard) {
    if (row == n) {
        result.add(ArraytoList(chessboard));
        return;
    }

    for (int col = 0;col < n; ++col) {
        if (isValid (row, col, n, chessboard)) {
            chessboard[row][col] = 'Q';
            backTrack(n, row + 1, chessboard);
            chessboard[row][col] = '.';
        }
    }

}

public List ArraytoList(char[][] chessboard) {
    List<String> list = new ArrayList<>();

    for (char[] c : chessboard) {
        list.add(String.copyValueOf(c));
    }
    return list;
}


public boolean isValid(int row, int col, int n, char[][] chessboard) {
    // 检查列
    for (int i=0; i<n; ++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;
}

} ```