织芜 2023-04-21 20:06 采纳率: 69.6%
浏览 22
已结题

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

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


#ifndef N_QUEENS_QUESTION 
#define  N_QUEENS_QUESTION 
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void n_queens(int n) {
    vector<vector<bool>> attack;    //攻击位置数组,0-安全,1-会受攻击
    vector<string> queen;     //皇后位置数组
    vector<vector<string>> 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]<attack.size()&& 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++) {
        vector<vector<bool>> 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
  • 写回答

2条回答 默认 最新

  • 个人练习生xx 2023-04-21 22:45
    关注

    这段代码的作用是解决 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()。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月30日
  • 已采纳回答 4月22日
  • 创建了问题 4月21日

悬赏问题

  • ¥15 如何删除这个虚拟音频
  • ¥50 hyper默认的default switch
  • ¥15 网站打不开,提示502 Bad Gateway
  • ¥20 基于MATLAB的绝热压缩空气储能系统代码咨询
  • ¥15 R语言建立随机森林模型出现的问题
  • ¥20 unity内置语言切换的按钮设置
  • ¥15 中级微观经济学,生产可能性边界问题
  • ¥15 TCP传输时不同网卡传输用时差异过大
  • ¥15 请各位看看我写的属于什么算法,或者有更正确的写法?
  • ¥15 html5 qrcode 扫描器