力扣 LeetCode 51. N皇后（Day14：回溯算法）

解题思路：

每次进入backtracking都表示进入下一行

每个backtracking中处理当前行的各个列，看各列是否合法

isValid中

因为是一行一行向下遍历的，所以对应的当前行一定满足条件，没有放置过其他皇后，只需要看对应的列是否满足即可

是否符合需要看左上45°和右上45°，之所以是往上看，是因为只有上才有先前放置过的皇后

class Solution {
    List<List<String>> res = new ArrayList<>();

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

    public void backtracking(char[][] board, int n, int row) {
        if (row == n) {
            res.add(formatConversion(board));
            return;
        }
        for (int i = 0; i < n; i++) { // i表示在当前row保持不变时的各个列
            if (isValid(board, n, row, i)) {
                board[row][i] = 'Q';
                backtracking(board, n, row + 1);
                board[row][i] = '.';
            }

        }
    }

    public List<String> formatConversion(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] c : board) {
            String s = new String(c);
            list.add(s);
        }
        return list;
    }

    public boolean isValid(char[][] board, int n, int row, int col) {
        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 - 1; i--, j++) {
            if (board[i][j] == 'Q')
                return false;
        }
        return true;
    }
}