棋盘上的智慧：N皇后问题回溯解法完全指南

一、问题背景

N皇后问题要求在N×N的棋盘上放置N个皇后，使得它们互不攻击（即不在同一行、列或对角线上）。这是回溯算法的经典案例，也是力扣面试08.12题的考察重点。

二、核心算法解析

1. 回溯框架

采用逐行放置策略，每行尝试所有可能列位置，通过递归探索解空间树

2. 冲突检测

三种冲突情况需要检查：

• 同列已有皇后

• 左上对角线已有皇后

• 右上对角线已有皇后

三、完整代码解析

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res; // 存储所有解
        vector<string> board(n, string(n, '.')); // 初始化n×n棋盘
        
        // 从第0行开始回溯
        backtrack(res, board, 0, n);
        return res;
    }

    // 回溯核心函数
    void backtrack(vector<vector<string>>& res, vector<string>& board, int row, int n) {
        if (row == n) { // 终止条件：成功放置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; // 通过所有检查
    }
};

四、关键技巧

1. 逐行处理：避免行冲突，只需处理列和对角线冲突

2. 即时回溯：发现无效路径立即返回，减少不必要的搜索

3. 空间优化：使用二维vector表示棋盘，直观清晰