思路：
N皇后问题要求在一个n×n的棋盘上放置n个皇后，使得它们不能相互攻击。皇后可以攻击同一行、同一列，以及两个对角线方向上的其他皇后。解决这个问题意味着找到所有可能的棋盘配置，每个配置都符合上述条件。
1、初始化数据结构
- 使用一个整型数组
record来记录每个皇后的位置。其中record[i] = j表示第i行的皇后位于第j列。 - 使用一个列表
list来收集所有有效的棋盘配置。
2. 递归和回溯
利用递归函数遍历棋盘的所有可能状态，对每一行尝试放置一个皇后，并通过回溯方法探索所有可能的解决方案：
- 递归函数定义：创建一个递归函数
process2(i, record, n, list)，其中i代表当前行，record用于记录皇后位置，n为棋盘大小，list用于存储所有合法的棋盘配置。 - 终止条件：当当前行
i等于n时，表示所有行都已经成功放置了皇后。此时根据record数组生成一个棋盘配置，加入到解决方案列表list中。
3. 验证放置是否有效
在递归中，对于每一行的每一列，检查放置皇后是否合法：
- 列冲突：确保没有其他皇后在同一列。
- 对角线冲突：确保没有其他皇后在两个可能的对角线上。
- 这可以通过检查当前尝试放置的列的索引与之前每行皇后列的索引的差的绝对值是否等于行的差的绝对值来实现。
4. 生成棋盘配置
每当找到一个有效的皇后布局后，需要将其转换为棋盘的字符串表示形式：
- 对于
record中的每个元素（表示列位置），构造一个字符串，其中'Q'表示皇后的位置，而'.'表示空位。
5. 回溯
- 每次尝试放置一个皇后后，进入下一行继续尝试。
- 如果发现当前行的某个列位置导致无法找到有效配置，则回溯到上一行，改变皇后的位置，然后再次尝试。
- 通过逐行递归和回溯，可以探索棋盘的所有可能状态，直到找到所有有效的解决方案。
通过这种结合递归与回溯的方法，N皇后问题可以被系统地解决，所有可能的棋盘配置都会被找到并记录。
class Solution {
// 主函数，用于解决n皇后问题，接收棋盘大小n，返回所有合法的棋盘配置
public List<List<String>> solveNQueens(int n) {
if (n < 1) {
return new ArrayList<>(); // 如果n小于1，直接返回空列表，因为没有可行的棋盘配置
}
int[] record = new int[n]; // 创建数组记录每一行皇后的列位置
List<List<String>> list = new ArrayList<>(); // 存储所有有效的棋盘配置
process2(0, record, n, list); // 从第0行开始递归处理放置皇后
return list; // 返回所有找到的棋盘配置
}
// 递归函数，用于处理从第i行开始的皇后放置
private void process2(int i, int[] record, int n, List<List<String>> list) {
if (i == n) { // 如果已经处理完所有行
List<String> childList = new ArrayList<>(); // 创建一个新的列表存储当前棋盘的一种配置
for (int index = 0; index < record.length; index++) { // 遍历每一行
int num = record[index]; // 获取当前行皇后的列位置
StringBuilder builder = new StringBuilder(); // 使用StringBuilder构建每一行的字符串表示
for (int j = 0; j < n; j++) { // 遍历每一列
if (j == num) {
builder.append('Q'); // 如果当前列是皇后的位置，添加'Q'
} else {
builder.append('.'); // 否则添加'.'
}
}
childList.add(builder.toString()); // 将构建好的字符串加入到当前棋盘配置中
}
list.add(childList); // 将当前配置添加到解决方案列表中
} else {
// 尝试在当前行i放置皇后的所有可能列
for (int j = 0; j < n; j++) {
if (isValid(record, i, j)) { // 检查在第i行的第j列放置皇后是否有效
record[i] = j; // 如果有效，记录这个位置
process2(i + 1, record, n, list); // 递归处理下一行
}
}
}
}
// 检查在第i行的第j列放置皇后是否会导致冲突
public static boolean isValid(int[] record, int i, int j) {
for (int k = 0; k < i; k++) { // 检查之前的每一行
// 判断列冲突和对角线冲突
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
return false; // 如果有冲突，返回false
}
}
return true; // 如果没有冲突，返回true
}
}
