n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
List<List<String>> ans = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
//. 代表未放置 Q 代表放置
char[][] panel = new char[n][n];
for (char[] c : panel) {
Arrays.fill(c, '.');
}
backTrack(n, 0, panel);
return ans;
}
public boolean isValid(char[][] panel, int row, int col) {
//横行
for(int i = 0; i < panel.length; i++) {
if (panel[row][i] == 'Q') {
return false;
}
}
//纵行
for(int i = 0; i < panel.length; i++) {
if (panel[i][col] == 'Q') {
return false;
}
}
// 左上
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (panel[i][j] == 'Q') {
return false;
}
}
// 右上
for (int i = row - 1, j = col + 1; i >= 0 && j < panel.length; i--, j++) {
if (panel[i][j] == 'Q') {
return false;
}
}
return true;
}
public void backTrack(int n, int row, char[][] panel) {
if (row == n) {
ans.add(array2list(panel));
return;
}
for (int col = 0; col < n; col++) {
if (isValid(panel, row, col)) {
panel[row][col] = 'Q';
backTrack(n, row + 1, panel);
panel[row][col] = '.';
}
}
}
public List array2list(char[][] panel) {
List<String> list = new ArrayList<>();
for (char[] c : panel) {
list.add(String.copyValueOf(c));
}
return list;
}
}
典型的回溯问题，利用回溯，每次判断当前这个位置可不可以放置，如果最后一排都放完了，就将答案传回去。