8*8 八皇后问题?
求各位路过的大神们指导!
本人在学习 8*8八皇后问题 时,写下以下代码,最终得到89个解,与标准答案92个解有差别,检查了很久都没有发现问题,特诚心来此求助!
用vector<int>表示一组解,初始化为{0,1,2,3,4,5,6,7},数组的下标代表行,对应的值表示列
#include <iostream>
#include <vector>
#include <set>
using namespace std;
class Solution{
public:
vector<vector<int>> vvi;
public:
void eightqueen(vector<int> &vec, int cur){
if(cur==vec.size()){
vvi.push_back(vec);
return;
}
for(int i=cur; i<vec.size();++i){
swap(vec[cur],vec[i]);
if(isdiagonal(vec,cur))
swap(vec[cur],vec[i]);
else{
eightqueen(vec,cur+1);
}
}
}
/**判断是否在对角线上,如果在,返回true*/
bool isdiagonal(vector<int> &vec, int cur){
if(cur==0)
return false;
for(int i=cur-1;i>=0;--i){
if((i-cur==vec[i]-vec[cur]) || (i-cur==vec[cur]-vec[i]))
return true;
}
return false;
}
};
int main(){
vector<int> vec = {0,1,2,3,4,5,6,7};
Solution s;
s.eightqueen(vec,0);
cout << "得到满足条件的排列共有:" << s.vvi.size() << endl;
for(auto e1 : s.vvi){
for(auto e2 : e1){
cout << e2;
}
cout << endl;
}
}