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;
    } 

}
全部评论
#include<iostream> using namespace std; int leftt[15]={0}; int rightt[15]={0}; int col[8]={0}; int Q[8]={0}; int cnt=1; void print(){     cout<<"第"<<cnt++<<"组解"<<endl;     for(int i=0;i<8;i++){         for(int j=0;j<8;j++){             if(Q[i]==j) cout<<"Q ";             else cout<<"X ";         }         cout<<endl;     }      } void Queen(){     int top=-1;     int i=0,j=0;     while(1){          while(top!=7){     for(;j<8;j++){             if(!col[j]&&!leftt[i+j]&&!rightt[7+i-j]){                 col[j]=leftt[i+j]=rightt[7+i-j]=1;                 Q[++top]=j;                 i++;                 j=0;                 break;             }         }         if(j==8){             j=Q[top];             if(top==-1)    break;             top--;                          i--;             col[j]=leftt[i+j]=rightt[7+i-j]=0;             j++;                 }                  }     if(top==-1)    break;     print();     j=Q[top];     top--;         i--;     col[j]=leftt[i+j]=rightt[7+i-j]=0;     j++;      } }           int main(void){     Queen();     return 0; }
点赞
送花
回复
分享
发布于 2018-09-04 11:40
你递归调用eightqueen之后也是要加一句swap复位的,不然整个都乱了。
点赞
送花
回复
分享
发布于 2018-09-06 01:11
滴滴
校招火热招聘中
官网直投
oj一发。。看看错的在哪呀😁
点赞
送花
回复
分享
发布于 2018-09-04 11:30
i应该从0开始吧,不应该从cur开始吧
点赞
送花
回复
分享
发布于 2018-09-06 00:20

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务