回溯法
题目
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
解题思路
本质 我们要找出所有将 n 个皇后放在 n×n 棋盘上的方式，使得没有任何两个皇后互相攻击。即：
- 每行只能有一个皇后
- 每列只能有一个皇后
- 每条斜线（45° 和 135°）只能有一个皇后
核心逻辑
- 从第一行开始，尝试在每一列放置皇后；
- 判断当前位置是否安全（即不在同一列、主对角线、副对角线上）；
- 如果安全，则继续在下一行递归放皇后；
- 如果放完了所有 n 个皇后，说明找到一个解，保存它；
- 回溯，撤销上一个放置，尝试别的列；
- 重复以上步骤直到遍历所有可能性。
代码实现
public class NQueens {
public List<List<String>> solveNQueens(int n) {
List<List<String>> results = new ArrayList<>();
char[][] board = new char[n][n];
// 初始化棋盘为全 '.'
for (char[] row : board) {
Arrays.fill(row, '.');
}
// 用来标记列、主对角线、副对角线是否被占用
boolean[] cols = new boolean[n];
boolean[] diag1 = new boolean[2 * n]; // 主对角线 (row - col + n)
boolean[] diag2 = new boolean[2 * n]; // 副对角线 (row + col)
backtrack(0, board, results, cols, diag1, diag2);
return results;
}
private void backtrack(int row, char[][] board, List<List<String>> results,
boolean[] cols, boolean[] diag1, boolean[] diag2) {
int n = board.length;
if (row == n) {
// 当前是一种有效解，转换成字符串保存
List<String> solution = new ArrayList<>();
for (char[] r : board) {
solution.add(new String(r));
}
results.add(solution);
return;
}
for (int col = 0; col < n; col++) {
// 计算主对角线和副对角线索引
int d1 = row - col + n;
int d2 = row + col;
// 如果该位置不安全，跳过
if (cols[col] || diag1[d1] || diag2[d2]) continue;
// 放置皇后并标记
board[row][col] = 'Q';
cols[col] = diag1[d1] = diag2[d2] = true;
// 递归处理下一行
backtrack(row + 1.md, board, results, cols, diag1, diag2);
// 回溯，撤销放置
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
}
回溯算法
核心逻辑
回溯法是一种系统地搜索所有可能解的算法，通过递归方式尝试所有可能性，如果当前选择不符合要求，就回退（回溯）到上一步，换个路径继续尝试。
本质思想
“尝试 + 判断（选择+剪枝） + 回退 + 继续尝试其他路径”
一般流程
void backtrack(状态参数...) {
if (到达终止条件) {
保存结果;
return;
}
for (可选的选择 : 所有选择集合) {
if (当前选择不合法) continue;
做选择;
backtrack(更新后的状态参数...);
撤销选择(回溯);
}
}