深搜练习(N皇后)(10)
一.题目
51. N 皇后 - 力扣（LeetCode）
二.思路讲解
2.1 思路讲解
N皇后问题是回溯算法的经典应用。我们采用逐行放置的策略：每一行只能放一个皇后，因此行冲突自然避免。接下来只需要确保放置的皇后不与之前任何皇后在同一列或同一对角线即可。为此，我们需要维护三个布尔数组（哈希表）来记录被占用的列、主对角线和副对角线。
列判断：用一个数组
checkCol记录哪些列已被占用。主对角线：在棋盘上，同一主对角线上的格子满足行号 - 列号为常数。由于这个差值可能为负数，我们统一加上一个偏移量（例如
n），映射到非负下标，用数组checkDig1记录。副对角线：同一副对角线上的格子满足行号 + 列号为常数，该值范围在
[0, 2n-2]，直接用数组checkDig2记录。
递归过程：从第 0 行开始，依次尝试每一列。如果当前位置的三个方向都未被占用，则放置皇后，并标记三个方向；然后递归处理下一行；递归返回后，撤销标记（回溯），继续尝试下一列。当成功放置完所有行时，将当前棋盘状态加入结果集。
剪枝：在尝试每一列时，若发现列或对角线已被占用，则直接跳过，不进入递归。这种提前判断避免了无效的放置，是回溯剪枝的典型应用。
三.代码演示
class Solution { public: bool checkCol[10],checkDig1[20],checkDig2[20];//x轴，主对角线，副对角线 vector<vector<string>>ret; vector<string>path; vector<vector<string>> solveNQueens(int n) { path.resize(n); for(int i = 0;i < n;i++) { path[i].append(n,'.');//初始化棋盘 } dfs(n,0); return ret; } void dfs(int n,int row) { if(row == n) { ret.push_back(path); return; } for(int col = 0;col < n;col++) { //剪枝判断x轴、主对角线、副对角线是否合法 if(checkCol[col] != true && checkDig1[row - col + n] != true && checkDig2[row + col] != true) { path[row][col] = 'Q'; checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;//表示使用 dfs(n,row + 1); //回溯 path[row][col] = '.'; checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;//表示空闲 } } } };四.代码讲解
一、全局变量设计
为了实现回溯并记录棋盘状态，我们定义以下成员变量：
checkCol[10]：布尔数组，记录每一列是否已被占用。由于 n ≤ 9，大小 10 足够。checkDig1[20]：布尔数组，记录每条主对角线是否已被占用。主对角线上的格子满足row - col为常数，范围[-(n-1), n-1]，加上偏移量n后映射到[1, 2n-1]，大小 20 足够。checkDig2[20]：布尔数组，记录每条副对角线是否已被占用。副对角线上的格子满足row + col为常数，范围[0, 2n-2]，大小 20 足够。ret：二维字符串数组，存储所有解，每个解是一个字符串向量（棋盘）。path：一维字符串数组，表示当前正在构建的棋盘（每一行是一个字符串）。
二、主函数solveNQueens
主函数接收整数n，首先将path大小调整为n，并用'.'初始化每一行的所有列，形成一个n × n的棋盘。然后调用递归函数dfs(n, 0)从第 0 行开始放置皇后，最后返回结果集ret。
三、递归函数dfs
递归函数dfs(int n, int row)的含义是：已经在前row行成功放置了皇后，接下来要在第row行放置皇后。执行流程如下：
1. 递归终止条件
当row == n时，说明所有 n 行都已成功放置皇后，得到一个完整解，将当前棋盘path的副本加入ret，然后返回。
2. 遍历列并尝试放置
使用for循环遍历当前行的每一列col（0 到 n-1）。对于每一列，检查当前位置是否与已放置的皇后冲突：
列冲突：
checkCol[col] == false主对角线冲突：
checkDig1[row - col + n] == false（加n防止负数下标）副对角线冲突：
checkDig2[row + col] == false
如果三个条件都满足（即均为false），则可以在(row, col)放置皇后：
将棋盘
path[row][col]设为'Q'。将三个方向标记为已占用：
checkCol[col] = true；checkDig1[row - col + n] = true；checkDig2[row + col] = true。递归调用
dfs(n, row + 1)，处理下一行。递归返回后，执行回溯：
将
path[row][col]恢复为'.'。将三个方向的标记恢复为
false，以便尝试其他列。
四、关键细节
数组大小：n ≤ 9 时，
row - col最小为-(n-1)，加n后最小为 1；最大为(n-1) + n = 2n-1 ≤ 17。row + col最大为2n-2 ≤ 16。因此checkDig1和checkDig2大小 20 足够。下标偏移：主对角线索引通过
row - col + n映射到非负范围，避免了负数下标。