回溯困难1 种解法
#51N 皇后
在 n × n 棋盘上放置 n 个皇后，使任意两个皇后不在同列或同一条对角线上。
#回溯#棋盘#剪枝
原题
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9
解题主线
- 按行递归后无需检查同行，只需记录列、主对角线 row - col 和副对角线 row + col 是否被占用。
- 两个对角线索引都可平移到 0 到 2n - 2 的数组范围。
- 完成第 n 行后必须保存棋盘并立即 return。
解法 1：按行回溯 + 占用数组
逐行选择列，使用三个 boolean 数组 O(1) 判断列和两类对角线冲突。
-
时间复杂度： O(n!)，按行且列不重复后的搜索树上界
-
空间复杂度： O(n²)，棋盘占 O(n²)，递归与占用数组占 O(n)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
final class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
if (n <= 0) {
return result;
}
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0, board, new boolean[n], new boolean[2 * n - 1],
new boolean[2 * n - 1], result);
return result;
}
private void backtrack(int row, char[][] board, boolean[] columns,
boolean[] diagonals, boolean[] antiDiagonals,
List<List<String>> result) {
int n = board.length;
// row 表示下一行待放置皇后，完成 n 行即得到一个合法方案
if (row == n) {
List<String> placement = new ArrayList<>(n);
for (char[] line : board) {
placement.add(new String(line));
}
result.add(placement);
return;
}
for (int column = 0; column < n; column++) {
// 平移主对角线索引，保证两类对角线都映射到非负数组下标
int diagonal = row - column + n - 1;
int antiDiagonal = row + column;
// 按行递归无需检查同行，只需剪掉列与两类对角线冲突
if (columns[column] || diagonals[diagonal] || antiDiagonals[antiDiagonal]) {
continue;
}
board[row][column] = 'Q';
// 棋盘与三组占用状态必须同步更新
columns[column] = diagonals[diagonal] = antiDiagonals[antiDiagonal] = true;
backtrack(row + 1, board, columns, diagonals, antiDiagonals, result);
// 回溯时完整恢复现场，供下一列复用
columns[column] = diagonals[diagonal] = antiDiagonals[antiDiagonal] = false;
board[row][column] = '.';
}
}
}实现提示
- 合并 char[][] 与 List 两种同构实现，保留更直接且冲突检查为 O(1) 的棋盘版本。
边界与易错点
- 旧 char[][] 版本在 row == n 保存结果后没有返回，随后访问 board[n] 会越界。
- 放置皇后后要同步设置三组占用状态，回溯时也必须全部清除。
- 结果中每一行要创建新 String，不能暴露之后还会修改的 char[]。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q051_NQueens.javabacktrack/Q051_nQueen.java