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

Question

这段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

Answer 1

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