C++算法与数据结构编写n皇后问题时出错

这段n皇后的代码有什么问题吗


#ifndef N_QUEENS_QUESTION 
#define  N_QUEENS_QUESTION 
#include
#include
#include<string>
using namespace std;
void n_queens(int n) {
    vectorbool>> attack;    //攻击位置数组，0-安全，1-会受攻击
    vector<string> queen;     //皇后位置数组
    vectorstring>> solve;     //解决方法数组

    //初始化
    for (int i = 0; i < n; i++) {
        vector<bool> a_line;
        for (int j = 0; j < n; j++) {
            a_line.push_back(false);
        }
        attack.push_back(a_line);

        string q_line;
        q_line.assign(n, '.');
        queen.push_back(q_line);
    }
    void back_track(int k, int n, vector<vector<bool>> &attack, vector<string> &queen, vector<vector<string>> &solve);
    back_track(1, n, attack, queen, solve);

    //展示结果
    cout << n << "皇后有" << solve.size() << "个解法，如下:" << endl;
    cout << "..........................................................." << endl;
    for (vector < vector<string>>::iterator it = solve.begin(); it != solve.end();it++) {
        for (vector<string>::iterator it2 = it->begin(); it2 != it->end(); it++) {
            cout << *it2 << endl;
        }
        cout << "..........................................................." << endl;
    }
}

void put_queen(int x,int y, vector<vector<bool>> &attack) {
    int direct_x[] = { -1,-1,-1,0,0,1,1,1 };           //x方向数组,长度为8
    int direct_y[] = { -1,0,1,-1,1,-1,0,1 };           //y方向数组,长度为8
    attack[x][y] = 1;

    for (int i = 1; i < attack.size(); i++) {          //每个方向最多前进i次
        for (int j = 0; j < 8; j++) {
            if(x + i * direct_x[j]>0&& x + i * direct_x[j]()&& y + i * direct_y[j]>0 && y + i * direct_y[j] < attack.size())
            attack[x + i * direct_x[j]][y + i * direct_y[j]] = 1;
        }
    }
}

void back_track(int k,int n, vector<vector<bool>> &attack, vector<string> &queen, vector<vector<string>> &solve){ //k-当前行数
    if (k == n+1) {
        solve.push_back(queen);
        return;  //递归边界
    }
    for (int i = 0; i < n; i++) {
        vectorbool>> tmp = attack;
        if (!attack[k][i]) {
            queen[k][i] = 'Q';
            put_queen(k, i, attack);
            back_track(k + 1, n,attack, queen, solve);  //归纳项
            attack = tmp;
            queen[k][i] = '.';   //若归纳项没能走到递归边界，则还原，试探这一层的下一个位置.
        }
    }
}
#endif

这段代码的作用是解决 n 皇后问题。但是在程序实现过程中，有以下问题：

1.头文件和没有使用，可以删除。

2.在put_queen函数中，如果x或y为0，数组下标就会越界，需要改为>=0。

3.在back_track函数中，递归边界应该是k>n，而不是k=n+1，因为当k=n时，还需要进行一次queen数组的赋值操作。

4.在back_track函数中，每进行一次put_queen函数的调用，用到的变量attack，需要备份一份，以免影响后面的操作。

5.在back_track函数中，若当前位置能够放置皇后，则应该进行下一次递归调用，而不是返回上一层，因为此时只是将这个皇后放置在当前位置，仍需尝试在下一行继续放皇后。

6.在展示结果的循环中，内部第二层循环应该遍历it->begin()到it->end()，而不是it到it->end()。

你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7674606
这篇博客你也可以参考下：C++蓝桥杯基础练习之2n皇后
除此之外, 这篇博客: 八皇后/N皇后问题 C++代码+解析（回溯与暴力法对比）中的 八皇后/N皇后问题 C++代码+解析 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

目的：掌握回溯法算法思想，并能利用回溯法算法思想解决实际问题。

任务：在 8×8 的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后，这就是一种符合条件的摆放方法。请求出总共有多少种不同的摆法。

**皇后的位置条件：**皇后可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。

判断皇后位置解决办法：
首先对于斜线上的元素满足：
①左上到右下对角线上xy差恒定
②右上到左下对角线上xy和恒定
所以我们可以设置两个数组，zhu和fu（取自主斜线副斜线线首字拼音）。分别用来保存已经放入皇后的坐标的差与和。
还有就是对当前列进行判断，该列上是否已经有皇后。这个判断比较简单，可以设置一个位置position数组，记录每个皇后的位置，扫描即可。

如何计算算法的执行时间：因为要观察算法执行完成的时间，故我使用了clock（）函数（其被ctime头文件收录）用来对算法执行的一段时间进行测量。通过设置两个clock_t类型的变量，也就是long类型，将他们放在算法代码的上下两端，最后用末减初得出的结果输出算法时间。

解题流程：
暴力法：
暴力法思想极为简单，由于棋盘为NN的，且不允许同一行有两个及以上皇后，所以，皇后应该为每行一个。我通过深度遍历枚举的方式，获得每行一个的所有皇后出现的可能性，然后对每一种可能进行判断是否为需要的结果。
容易看出，该算法时间复杂度极高。单纯的所有位置的组合就有N^N次方种。还有判断是否合适需要对每种可能进行判断，因为我使用了哈希表，所以判断的代价较低，对于每个的判断有O（1）的复杂度
回溯法：
大致思想为，设置一个NN的vector，用于保存一个答案的结果。还有一个保存最终所有解的数据结构，使用vector<vector>保存所有解。
我们按照行优先遍历的方式。从[0][0]号位置开始，如果在某一行找到了一个可以放置皇后的位置，记录该行的位置，并且更新相应的三个位置数组（zhu，fu，position，以后用三个位置数组代替）那么进入下一行进行判断。如果在某行没有找到位置，那么意味着前面发生了错误，需要返回上一行进入该行的位置，将保存的上一行皇后的位置从三个位置数组中删除，接着判断上一行下一个未判断的空位。
如果在最后一行找到了位置，那么意味着找到了一个解，接着保存该解。并且删除三个位置数组的位置，回溯至上一级，返回上一行对未判断的位置继续进行求解。直至对第一行所有位置扫描一遍后，找到所有解为止。

定义的数据结构的功能：
在这里插入图片描述

函数的功能：
在这里插入图片描述

两种算法的伪代码：

//回溯法伪代码
bool  DFS(int x,int y,int n)：
if(x>=n||y>=n)    //越界退出
   return false
for i←0 to n-1 do
  if(!isok(x,i))     //如果（x,y）位置不能放皇后则判断下一个位置,如果可以isok函数会更新三个位置数组的信息
     continue
  if(x==n-1)     ///遍历到了最后一行，且最后一行也放上了皇后，成功找到
     return true
if(DFS(x+1,0,n))     //DFS返回true，找到一个答案，需要保存答案
   get_ans()       //保存答案
   pop_array()     //放弃最后一行的答案，回溯至上一行，看看还有没有其他答案。
pop_array()     //在某一行没有适当的位置时，需要回溯。或者已经找到最终答案，对倒数第二行及以上行没有判断的位子进行重新判断。需要弹出最后加入的元素
return false      //如果该行没有适合的，返回失败



//暴力法伪代码,获取全部可能方案
void DFS2（int x,int y,int n）:
if(x>=n||y>=n)    //越界退出
   return
    position.push_back((x,y))    //保存当前（x,y)
if(x==n-1)     //找到了一组可能解
   if(isok_method2(position))    //如果该组解是符合题意的解,就保存该解
          result.push_back(position)      
       
   position.pop_back()//更新位置(最后一行返回的位置)
   return
row=x+1
for i←0 to n-1 do:    //从该行的第0个到n-1个开始
   DFS(row,i,n)
   if(row!=n-1)
      position.pop_back()     //删除position(x,y)

附录，源代码：


#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<ctime>
#include<map>
#include <utility>
using namespace std;
class NQueens {
public:
    vector<vector<string>> result;  //结果，皇后的位置用Q表示，其他用‘.’，每N个元素为一组答案
    vector<vector<pair<int, int>>> TEMP;
    vector<pair<int, int>> position;//皇后的位置
    vector<int> zhu;//左上到右下对角线上xy差恒定
    vector<int> fu;//右上到左下对角线上xy和恒定
    int N;//皇后数量

    void solveNQueens(int n) {

        N = n;

        if (n == 1)   //不需要进入其他行判断，直接返回结果
        {
            vector<string> temp;
            temp.push_back("Q");
            result.push_back(temp);
            return;
        }

        for (int i = 0; i < n; i++)  //第一行从左到右都试试
        {
            zhu.push_back(-i);
            fu.push_back(i);
            pair<int, int> temp(0, i);
            position.push_back(temp);
            DFS(1, 0);
            //清空三个数组
            pop_array(false);
        }

    }

    
    void method2_solveNQueens(int n)   //暴力解出全部可能排序,排列方法,所有结果存入result中
    {
        N = n;
        if (n == 1)  //n==1特殊的情况，直接返回结果即可
        {
            vector<string> temp;
            temp.push_back("Q");
            result.push_back(temp);
            return;
        }

        for (int i = 0; i < n; i++)//获得N个皇后所有可能的位置，每行1个。
        {
            DFS2(0, i);
            position.pop_back();
        }

        int count = 0;  //删除的时候result会变化，所以设置一个count用来同步TEMP和result
        vector<vector<string>>::iterator it;
        for (int i = 0; i < TEMP.size(); i++)  //对每种可能进行判断，看其是否为答案
        {
            if (!isok_method2(TEMP[i]))   //不是解就在得到的可能中删除
            {
                it = result.begin();
                it = i - count+it;    //TM的，it+i-count就不对，有可能先算到it+i就越界了，shabi编译器
                result.erase(it);
                count++;
            }
        }

        
    }




    bool DFS(int x, int y) {    //行优先遍历，在该行找到了皇后的位置便进入下一行

        if (x >= N || y >= N)//越界
            return false;

        for (int i = 0; i < N; i++)   //对该行遍历
        {
            if (!isok(x, i))//如果位于一列或者同一对角线则该位置不能放置，换个位置,如果可以的话，就更新三个数组
                continue;

            //进入这里证明在该行找到了合适的位置，判断是否完成

            if (x == N - 1)//遍历到了最后一行，且最后一行也放上了皇后，成功找到
                return true;

            //到这里表示在该行找到了合适位置，且未完成，进入下一行判断

            if (DFS(x + 1, 0))  //从下一行第一个开始，x行y列
            {
                //若到了最后一行结束时，会返回true，从而可以调用get_ans得到答案。（只有获得一个最终答案时才会进入到这里）
                get_ans();   //保存答案
                pop_array(true);  //放弃最后一行的答案，回溯至上一行，看看还有没有其他答案。
            }

            //在某一行没有适当的位置时，需要回溯。或者已经找到最终答案，对倒数第二行及以上行没有判断的位子进行重新判断。
            pop_array(true);
        }
        //如果该行没有适合的，返回失败
        return false;
    }

    //方法二的DFS
    void DFS2(int x, int y)   //找到所有可能位置
    {
        if (x >= N || y >= N)  //越界
            return;

        pair<int, int> temp(x, y);
        position.push_back(temp);

        if (x == N - 1)   //找到一种可能
        {
            get_ans();   //转为字符串方便显示
            TEMP.push_back(position);    //TEMP记录每个可能的位置
            position.pop_back();   //更新位置(最后一行返回的位置)
            return;
        }
        int row = x + 1;
        //从该行的第0个到n-1个开始
        for (int i = 0; i < N; i++)
        {
            DFS2(row, i);
            if (row != N - 1)
                position.pop_back();  //删除position(x,y)
        }

    }


    map<int, bool> hash1;
    map<int, bool> hash2;

    //对方法二找到每个结果进行判断，是否符合要求
    bool isok_method2(vector<pair<int, int>> &temp)
    {
        hash1.clear();  //先清空
        hash2.clear();
        for (int i = 0; i < N; i++)  //判断是否有在相同列上的
        {
            if(hash1.count(temp[i].second))
                return false;
            hash1.insert(map<int, int>::value_type(temp[i].second, 0));
        }
        hash1.clear();
        for (int i = 0; i < N; i++)  //判断斜线上的
        {
            if(hash1.count(temp[i].first-temp[i].second)|| hash2.count(temp[i].first + temp[i].second))  //找到了在对角线上已经存在的元素，则返回false
                return false;
            hash1.insert(map<int,int>::value_type(temp[i].first - temp[i].second,0));
            hash2.insert(map<int, int>::value_type(temp[i].first + temp[i].second,0));
        }


        return true;
    }



    //判断位置是否可以放置皇后，并且更新相应数组
    bool isok(int& x, int& y)
    {
        for (int i = 0; i < zhu.size(); i++)    //是否在两个方向的斜线上有皇后
            if ((x - y) == zhu[i] || (x + y) == fu[i])
                return false;

        for (int i = 0; i < position.size(); i++)   //判断一列上是否有
            if (y == position[i].second)
                return false;

        zhu.push_back(x - y); fu.push_back(x + y);    //该位置可以放置皇后，更新zhu fu和position数组
        pair<int, int> temp(x, y);
        position.push_back(temp);

        return true;
    }

    //获得答案,每一个position对应一个解，将其转为字符串可视化的形式
    void get_ans()
    {
        vector<string> temp;
        string tmp;
        for (int i = 0; i < position.size(); i++)
        {
            for (int i = 0; i < N; i++)
                tmp += '.';
            tmp[position[i].second] = 'Q';
            temp.push_back(tmp);
            tmp = "";
        }
        result.push_back(temp);
    }

    //对三个数组撤销操作
    void pop_array(bool flag)
    {
        if (flag==true) {    //为1表示撤销上一级操作
            position.pop_back();
            zhu.pop_back(); fu.pop_back();
        }
        else   //清空
        {
            zhu.clear();
            fu.clear();
            position.clear();
        }
    }
    //输出答案
    void print_result()
    {
          //输出结果一的答案
            cout << "**********************" << endl;
            cout << "答案共有" << result.size() << "个,如下：" << endl;
            cout << "**********************" << endl;

            for (int i = 0; i < result.size(); i++)
            {
                cout << "答案" << i + 1 << "如下：" << endl;
                for (int j = 0; j < N; j++) {
                    cout << result[i][j] << endl;
                }
                cout << "**********************" << endl;
            }
        
        cout << "输出结束！！！！"<<endl;
    }
};

int main()
{
    cout << "请输入皇后的个数:";
    int n;
    cin >> n;
    clock_t start, end;;
    NQueens queen,queentwo;   

    //回溯
    start = clock();
    queentwo.solveNQueens(n);// queentwo.print_result();
    end = clock();

    cout << "当皇后数量为" << n << "个时采用回溯解法时间为:" << (double)(end - start) / CLOCKS_PER_SEC << "S" << endl;

    //暴力
    start = clock();
    queen.method2_solveNQueens(n);
   // queen.print_result();
    end = clock();

    cout << "当皇后数量为" << n << "个时采用暴力解法时间为:" << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;

    cout << endl << "***************" << endl;
    cout << "回溯法的结果共有：" << queentwo.result.size() << "种" << endl<<"每种情况为：";
    queentwo.print_result();
    cout << endl <<"***************"<< endl;
    cout << "暴力法的结果共有：" << queen.result.size() << "种" << endl << "每种情况为：" << endl;
    queen.print_result();

    cout << endl << "***************" << endl;

    return 0;
}

以下回答由chatgpt基于相关博客总结生成:
很抱歉，参考资料中并没有与n皇后问题相关的内容，无法为您提供更准确的解决方案。请提供相关错误信息或代码，以便我们更好地帮助您解决问题。

C++算法与数据结构 编写n皇后问题时出错

C++算法与数据结构编写n皇后问题时出错