# C++算法与数据结构 编写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()。

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

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

#### 悬赏问题

• ¥15 Matlab安装yalmip和cplex功能安装失败
• ¥15 加装宝马安卓中控改变开机画面
• ¥15 STK安装问题问问大家，这种情况应该怎么办
• ¥15 更换了一个新的win10系统，再下载VS时碰到的问题，是C++组件的？
• ¥15 关于罗技鼠标宏lua文件的问题
• ¥15 halcon ocr mlp 识别问题
• ¥15 已知曲线满足正余弦函数，根据其峰值，还原出整条曲线
• ¥20 无法创建新的堆栈防护界面
• ¥15 sessionStorage在vue中的用法
• ¥15 wordpress更换域名后用户图片头像不显示