51. N 皇后
根据 n 创建一个二维数组，填充满 '.'。在每一行选中一个位置放入皇后，如果合法的话，就继续递归探测下一行，因为不能再放在当前行，放在当前行冲突。
注意 for 循环遍历的是列，递归遍历的是行。
支持的回溯问题操作的都是以为数组，这里开始操作二维数组，理解决策树的宽和高是什么很重要。
class Solution {
List<List<String>> res = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
// 填充二维数组
for (char[] b: board) {
Arrays.fill(b, '.');
}
backtrace(board, 0);
return res;
}
public void backtrace(char[][] board, int row) {
int n = board.length;
// 放完 n 个皇后，收集答案
if (row == n) {
res.add(mapToList(board));
return;
}
for (int col = 0; col < board.length; col++) {
// 检查皇后放在 [row, col] 是否合法
if (isValid(board, row, col)) {
// 合法，再将 Q 放入
board[row][col] = 'Q';
// row + 1，递归处理下一行
backtrace(board, row + 1);
// 回溯
board[row][col] = '.';
}
}
}
// 检查 [row, col] 位置放置皇后的话是否合法
public boolean isValid(char[][] board, int row, int col) {
int n = board.length;
// 不用检查行，因为我们知道不能放在同一行，根本不会往行上放皇后，代码都是递归写的，直接考虑往下一行放皇后
// 检查列（列不动，遍历行）
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}
// 检查 45 度角（只关注前面的元素）
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
// 检查 135 度角（只关注前面的元素）
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
public List<String> mapToList(char[][] board) {
List<String> list = new LinkedList<>();
for (char[] b: board) {
StringBuilder sb = new StringBuilder();
for (char c : b) {
sb.append(c);
}
list.add(sb.toString());
}
return list;
}
}