深搜练习(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轴主对角线副对角线 vectorvectorstringret; vectorstringpath; vectorvectorstring 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循环遍历当前行的每一列col0 到 n-1。对于每一列检查当前位置是否与已放置的皇后冲突列冲突checkCol[col] false主对角线冲突checkDig1[row - col n] false加n防止负数下标副对角线冲突checkDig2[row col] false如果三个条件都满足即均为false则可以在(row, col)放置皇后将棋盘path[row][col]设为Q。将三个方向标记为已占用checkCol[col] truecheckDig1[row - col n] truecheckDig2[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映射到非负范围避免了负数下标。