NQUEENS问题的C++递归解决方案无法正常工作

Question

我正在尝试解决著名的 NQUEENS使用 vector 和类在 C++ 中使用回溯的问题。但它在某些情况下(例如 5)和其余情况(例如 4)给出了正确的结果，它显示“解决方案不存在”。

我的代码如下: 用于存储皇后位置的行和列的类声明。

class position
{
public:
    int r,c;
    position(int r,int c)
    {
        this->r=r;
        this->c=c;
    }
};

递归函数:

vector<position> positions;
bool solve(int n, int r)
{
    if(r==n)
        return true;
    for (int c = 0; c < n; ++c)
    {
        bool safe=true;

        for(int q=0;q<r;++q)
        {
            if (positions[q].c == c || positions[q].r - positions[q].c == r - c 
                || positions[q].r + positions[q].c == r + c) 
            {
                    safe = false;
                    break;
            }
        }
        if(safe)
        {
            position p(r,c);
            positions.push_back(p);
            if(solve(n,r+1))
                return true;
        }
    }
    return false;
}

驱动函数如下:

int main()
{
    int n;
    cin>>n;
    if(!solve(n,0))
    {
        cout<<"Solution doesn't exist"<<endl;
        return 0;
    }
    printboard(n);
    return 0;
}

请帮我解决这个问题。

Answer 1

if(solve(n,r+1))
  return true;
else
    positions.erase(positions.begin()+positions.size()-1);

如果一个单元格的解决方案不存在，则从可能的位置删除该单元格以避免碰撞。 编辑:- 谢谢Mr.Bo R 的指正。