递归模板

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

N皇后

1.1 思路

1) 知识点

如果使用暴力枚举，时间复杂度将达到n的n次方，需要对遍历部分进行优化处理，即 "剪枝" 。想到应该使用递归来做，在一条分支不成立后，直接跳回上一行进行判断。

2) 遍历思路

按行递归放皇后 → 每列逐个尝试 → 不合法就回溯。

• 从第 0 行开始，每一行依次尝试在不同列放置皇后。

• 每放一个皇后，都检查当前放置是否合法（同列、两条对角线不能有其他皇后）。

• 如果合法，就递归到下一行继续放置下一个皇后。

• 如果到达最后一行（row == n），说明找到了一种可行解，将当前棋盘保存。

• 如果某一行没有合法位置，就回溯到上一行，撤回上一个皇后，继续尝试下一列。

3) 递归模板

1. 递归方法形参

在思考了递归中的内容后，知道需要传入当前行row、棋盘长度n、棋盘chessBoard

public void backTrack(int n, int row, char[][] chessBoard){

    ... ...

}

2. 判断终止条件

能够放置皇后，直至最后一行，即row == n

说明这是一个可行解，记录当前棋盘情况，并放到结果集中

需要知道：当前行row、棋盘长度n、棋盘chessBoard

if(row == n){
    res = push_back(chessBoard);
    return;
}

3. for循环

for中遍历的应该是当前行的所有列，从0一直遍历到棋盘边界

需要知道：棋盘长度n

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

4. 处理节点

1. 当前坐标是否放置皇后：

   1. 如果能放，进入下一行

   2. 不能放，回溯到上一行对应列的下一列

2. 会想到：

   1. 通过编写一个方法isValid判断当前位置放置皇后是否合理

   2. 方法形参：

      • 当前横坐标：row

      • 当前纵坐标：col

      • 当前棋盘情况：chessBoard

      • 棋盘长度：n

5. 递归

当前行皇后被放置到合理位置：进入下一行

递归：调用当前方法，传参的行数row+1

backTrack(n, row + 1, chessBoard);

6. 回溯（撤销选择）

由于需要遍历所有的可行解，在找到一组可行解后，返回上一层，撤销当前行放置的皇后，尝试下一列位置

chessBoard[row][i] = '.';

1.2 代码实现

class Solution {

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

    public List<List<String>> solveNQueens(int n) {
        char[][] chessBoard = new char[n][n];
        for(char[] c : chessBoard) {
            Arrays.fill(c,'.');
        }
        backTrack(n, 0, chessBoard);
        return res;
    }

    public void backTrack(int n, int row, char[][] chessBoard) {
        if(row == n) {
            res.add(push_back(chessBoard));
            return;
        }
        for(int i = 0; i < n; i ++){    // 遍历当前行的对应列
            if(isValid(row,i,chessBoard,n)){
                chessBoard[row][i] = 'Q';   // 放置皇后
                backTrack(n, row+1, chessBoard);
                chessBoard[row][i] = '.';   // 回溯皇后
            }
        }
    }

    //存放合理皇后的解
    public List push_back(char[][] chessBoard) {
        List<String> list = new ArrayList<>();
        for(char[] c : chessBoard) {
            list.add(String.valueOf(c));
        }
        return list;
    }

    // 判断当前位置是否放置皇后
    public Boolean isValid(int row, int col, char[][] chessBoard, int n) {

        // 判断列
        for(int i = row-1; i >= 0; i --) {
            if(chessBoard[i][col] == 'Q') {
                return false;
            }
        }
        // 判断左上
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j --) {
            if(chessBoard[i][j] == 'Q') {
                return false;
            }
        }
        // 判断右上
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j ++) {
                        if(chessBoard[i][j] == 'Q') {
                return false;
            }
        }
            return true;
    }
}