题解 | N皇后问题

class Solution {
  public:
    int Nqueen(int n) {
        int count = 0;
        vector<int> position(n, 0); // position[i]表示第i行皇后放在第几列
        backtrack(0, n, position, count);
        return count;
    }

  private:
    void backtrack(int row, int n, vector<int>& position, int& count) {
        if (row == n) {
            // 所有行都放置完毕，找到一个解
            count++;
            return;
        }

        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, position)) {
                position[row] = col; // 放置皇后
                backtrack(row + 1, n, position, count); // 递归到下一行
                // 回溯：不需要显式重置position[row]，因为会被覆盖
            }
        }
    }

    bool isValid(int row, int col, const vector<int>& position) {
        // 检查当前位置(row, col)是否合法
        for (int i = 0; i < row; i++) {
            // 检查是否在同一列
            if (position[i] == col) {
                return false;
            }
            // 检查是否在同一对角线：行差 == 列差
            if (abs(row - i) == abs(col - position[i])) {
                return false;
            }
        }
        return true;
    }
};

// 共同的回溯框架
void backtrack(当前状态) {
    if (到达终止条件) {
        记录解;
        return;
    }
    
    for (所有可能的选择) {
        if (选择合法) {
            做选择;
            backtrack(下一状态);
            撤销选择;
        }
    }
}

全排列和N皇后问题回溯都是自动的,递归调用返回时都发生回溯;制权都返回到上一层的for循环;会继续尝试下一个选择
撤销操作不是"不自动回溯"的证据，而是不同状态管理策略的体现。回溯的核心机制——递归返回后继续循环——在两种算法中是完全相同的!
撤销选择更深层的设计原则：
何时需要显式撤销？
状态会累积或影响后续决策
状态改变是添加式的而非替换式的
状态需要在回溯后恢复到之前的确切值

何时可以依赖覆盖？
每个决策点的状态是独立的
状态存储是固定大小的数组
新的选择会自然覆盖旧的选择