时间戳

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

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

问题描述

我正在尝试使用向量和类在 C++ 中使用回溯来解决著名的NQUEENS问题。但它在某些情况下（例如 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;
}

请帮我解决这个问题。

标签： c++algorithmbacktracking

解决方案

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

如果一个单元格的解决方案不存在，则从可能的位置擦除该单元格，以避免冲突。编辑：- 感谢 Bo R 先生的更正。

推荐阅读