N皇后问题C++代码仅支持n≤4，n=6时出现段错误求助

我正在解决N皇后问题（给定整数n，找出在n×n棋盘上放置n个皇后且互不攻击的所有方式）。代码在n≤4时运行正常，但当n=6、棋盘状态为[0,2,4]时，尝试在下一行第1列放置皇后会触发段错误，无法定位原因（此时集合rem并非空）。使用vector存储结果，其中第i个元素表示第i行皇后所在的列位置，代码包含大量调试用打印语句：

#include<iostream>
#include <vector>
#include <set>

using namespace std;


bool isLegal(vector<int> &board) {
    
    int i = board.size() - 1;
    for (int j=0; j<board.size() - 1; ++j) {
        if (board[i] - board[j] == i - j || board[i] - board[j] == j - i ) {
            return false;
        }
    }
    
    return true;
}

void print(vector<int> &board) {
    for(auto col : board) {
        cout<< col<< "  ";
    }
    cout<< endl; 
}
void print(set<int> &rem) {
    for(auto col : rem) {
        cout<< col<< "  ";
    }
    cout<< endl; 
}

void putQueen(set<int> &rem, vector<int> &board, vector<vector<int>> &ans) {
    cout<< "Call on board  ";  
    print(board);

    if (rem.empty()) {
        ans.push_back(board);
        cout<< "Got answer"<< endl;
        return;
    }

    for (auto p=rem.begin(); p!=rem.end(); ++p) {
        cout<< "Trying : ";
        int col = *p;
        cout<< col<< endl;

        cout<< "Remaining Columns : ";
        print(rem);

        board.push_back(col) ;
        cout<< "Put in "<< col<<endl;
        cout<< "C1"<< endl;
        rem.erase(col);
        cout<< "C2"<< endl;
        print(board);
        if (isLegal(board)) {
            putQueen(rem, board, ans);
        }
        cout<< "C3"<< endl;
        rem.insert(col);
        
        board.pop_back();
        cout<< "C4"<< endl;

        cout<< "Remaining Columns : ";
        print(rem);
        cout<< "Board : ";
        print(board);

        cout<< "Col at"<< col<< endl;
    }
}

vector<vector<int>> findPositions(int n) {
    vector<vector<int>> ret;
    set<int> rem ;

    for (int i=0; i<n; ++i) {
        rem.insert(i);
    }

    vector<int> board;

    cout<< "Call 1"<<endl;
    putQueen(rem, board, ret);

    return ret;
}

int main() {
    int n;
    cin >> n;
    /*
    [1, 3, 0, 2] -> col
     0, 1, 2, 3  -> row
    */
    vector<vector<int>> ans = findPositions(n);

    cout<< ans.size()<< endl;

    for (auto board : ans) {
        for (auto pos : board) {
            cout<< pos<< "  "; 
        }
        cout<< endl;
    }

    return 0;
}

问题原因 #

核心问题是遍历set时直接修改set导致迭代器失效：在putQueen的for循环中，使用auto p=rem.begin(); p!=rem.end(); ++p遍历set，但循环内执行了rem.erase(col)和rem.insert(col)操作。当erase删除当前迭代器指向的元素时，该迭代器会立即失效，后续的++p会访问无效内存，触发段错误。

比如n=6、棋盘为[0,2,4]时，rem剩余列是1、3、5。遍历到col=1时，执行rem.erase(1)后，迭代器p已失效，下一次循环的++p会非法访问内存，直接引发段错误。

修复方案 #

方案1（推荐）：遍历临时副本

遍历前将set的元素复制到临时vector中，遍历副本而非原set，这样修改原set不会影响遍历过程：

修改putQueen函数中的循环部分：

// 替换原for循环
vector<int> cols(rem.begin(), rem.end());
for (int col : cols) {
    cout<< "Trying : ";
    cout<< col<< endl;

    cout<< "Remaining Columns : ";
    print(rem);

    board.push_back(col) ;
    cout<< "Put in "<< col<<endl;
    cout<< "C1"<< endl;
    rem.erase(col);
    cout<< "C2"<< endl;
    print(board);
    if (isLegal(board)) {
        putQueen(rem, board, ans);
    }
    cout<< "C3"<< endl;
    rem.insert(col);
    
    board.pop_back();
    cout<< "C4"<< endl;

    cout<< "Remaining Columns : ";
    print(rem);
    cout<< "Board : ";
    print(board);

    cout<< "Col at"<< col<< endl;
}

方案2：利用erase返回值更新迭代器

调整循环结构，使用erase的返回值获取下一个有效迭代器，避免迭代器失效：

// 替换原for循环
for (auto p=rem.begin(); p!=rem.end();) {
    int col = *p;
    cout<< "Trying : ";
    cout<< col<< endl;

    cout<< "Remaining Columns : ";
    print(rem);

    board.push_back(col) ;
    cout<< "Put in "<< col<<endl;
    cout<< "C1"<< endl;
    p = rem.erase(p); // erase返回下一个有效迭代器
    cout<< "C2"<< endl;
    print(board);
    if (isLegal(board)) {
        putQueen(rem, board, ans);
    }
    cout<< "C3"<< endl;
    rem.insert(col);
    
    board.pop_back();
    cout<< "C4"<< endl;

    cout<< "Remaining Columns : ";
    print(rem);
    cout<< "Board : ";
    print(board);

    cout<< "Col at"<< col<< endl;
    // 无需手动++p，erase已返回下一个迭代器
}

修改后效果 #

两种方案都能解决迭代器失效问题，n=6时可以正常运行并输出所有合法的N皇后布局。

内容的提问来源于stack exchange，提问作者Priyanshu Sahani