解题思路：
每次进入backtracking都表示进入下一行
每个backtracking中处理当前行的各个列，看各列是否合法
isValid中
因为是一行一行向下遍历的，所以对应的当前行一定满足条件，没有放置过其他皇后，只需要看对应的列是否满足即可
是否符合需要看左上45°和右上45°，之所以是往上看，是因为只有上才有先前放置过的皇后
注意终止条件row == n，而不是row == n-1，row 表示当前准备放皇后的行。当 row == n-1时，最后一行还没放皇后
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; } }
