力扣面试08.12题解析：N皇后问题的回溯法高效解题（C++代码实现）
一、题目解读
力扣面试08.12题要求解决经典的N皇后问题：在n×n的棋盘上放置n个皇后，使得任意两个皇后不处于同一行、列或对角线上。题目需要返回所有可能的合法布局，通常使用回溯算法进行求解。该问题考验对递归、状态空间搜索及冲突检测的理解，是算法面试中的常见题型。
二、解题思路
采用回溯法（Backtracking）求解。核心思想是：逐行尝试放置皇后，每放置一个皇后后，递归处理下一行，同时利用剪枝策略（即isValid函数）判断当前位置是否合法。若找到完整解，则保存结果；若当前行无法放置，则回溯至上一步重新选择位置。通过深度优先搜索遍历所有可能的状态空间，最终得到全部合法解。
三、解题步骤解析
1. 初始化棋盘：创建n行n列的二维字符数组，初始元素均为'.'（表示空位）。
2. 递归入口：调用backtrack函数，从第0行开始递归，参数包括结果集res、当前棋盘board、当前行row及棋盘大小n。
3. 逐行放置皇后：在每一行中遍历所有列（col=0到n-1），若当前位置合法（通过isValid判断），则：
放置皇后：board[row][col] = 'Q'。
递归下一行：backtrack(res, board, row+1, n)。
回溯撤销：board[row][col] = '.'（恢复为原状态）。
4. 终止条件：当row达到n时，说明已找到一组合法解，将当前棋盘存入结果集res。
5. 合法性检查（isValid函数）：
列冲突：检查当前列是否有其他皇后（遍历上方各行）。
对角线冲突：分别检查左上和右上对角线是否有皇后（利用坐标偏移判断）。
四、代码及注释
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> board(n, string(n, '.')); // 初始化棋盘
backtrack(res, board, 0, n);
return res;
}
void backtrack(vector<vector<string>>& res, vector<string>& board, int row, int n) {
if (row == n) { // 找到一个解
res.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (isValid(board, row, col, n)) {
board[row][col] = 'Q'; // 放置皇后
backtrack(res, board, row + 1, n); // 递归下一行
board[row][col] = '.'; // 回溯
}
}
}
bool isValid(vector<string>& board, int row, int col, int n) {
// 检查列是否有冲突
for (int i = 0; i < row; ++i) {
if (board[i][col] == 'Q') return false;
}
// 检查左上对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 'Q') return false;
}
// 检查右上对角线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 'Q') return false;
}
return true;
}
};注释说明：代码中已嵌入关键步骤注释，清晰标注递归逻辑、回溯操作及合法性判断的细节。
五、总结
本文通过回溯算法解决了N皇后问题，其关键在于逐行递归+冲突剪枝的策略。时间复杂度为O(n!)（需遍历所有排列），但通过提前判断合法性可大幅减少无效搜索。该解法虽非最优，但易于理解和实现，适合面试场景。实际应用中可结合位运算或迭代优化进一步提升效率。掌握此类问题有助于强化递归思维与算法设计能力。
原创内容 转载请注明出处
