注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

C++解8皇后问题[练习]  

2010-10-07 02:48:27|  分类: practice |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

C++8皇后问题

         关于什么是8皇后问题请自行google,本程序全是无事的练习J

#include<iostream>

#include<algorithm>

#include<vector>

#include<iterator>

using namespace std;

inline bool check_valid(vector<int>& input,vector<vector<int> >& result)

{

    for(int i=1;i<input.size();++i)

    {

        for(int j=0;j<i;++j)//check previous state

        {

            if(i-j==input[i]-input[j] || j-i==input[i]-input[j]) // cross state

            {

                //drop all tail permuation's(they can't be usefule)

                sort(input.begin()+i+1,input.end(),[&](int& x,int& y)->bool{if(x>y){return true;}else{return false;}});

                return false;

            }

        }

    }

    result.push_back(input);

    return true;

}

int main()

{

    vector<int> v_row;

    vector<vector<int> > result;

    for(int i=0;i<8;++i)

    {

        v_row.push_back(i);

    }

    do

    {

        check_valid(v_row,result);

    }while(next_permutation(v_row.begin(),v_row.end()));

    cout<<"result count:"<<result.size()<<endl;

    for(int i=0;i<result.size();++i)

    {

        copy(result[i].begin(),result[i].end(),ostream_iterator<int>(cout," "));

        cout<<endl;

    }

}

 

结果为92组,其依次为07,纵坐标可行解为下列结果。
result count:92

0 4 7 5 2 6 1 3

0 5 7 2 6 3 1 4

0 6 3 5 7 1 4 2

0 6 4 7 1 3 5 2

1 3 5 7 2 0 6 4

1 4 6 0 2 7 5 3

1 4 6 3 0 7 5 2

1 5 0 6 3 7 2 4

1 5 7 2 0 3 6 4

1 6 2 5 7 4 0 3

1 6 4 7 0 3 5 2

1 7 5 0 2 4 6 3

2 0 6 4 7 1 3 5

2 4 1 7 0 6 3 5

2 4 1 7 5 3 6 0

2 4 6 0 3 1 7 5

2 4 7 3 0 6 1 5

2 5 1 4 7 0 6 3

2 5 1 6 0 3 7 4

2 5 1 6 4 0 7 3

2 5 3 0 7 4 6 1

2 5 3 1 7 4 6 0

2 5 7 0 3 6 4 1

2 5 7 0 4 6 1 3

2 5 7 1 3 0 6 4

2 6 1 7 4 0 3 5

2 6 1 7 5 3 0 4

2 7 3 6 0 5 1 4

3 0 4 7 1 6 2 5

3 0 4 7 5 2 6 1

3 1 4 7 5 0 2 6

3 1 6 2 5 7 0 4

3 1 6 2 5 7 4 0

3 1 6 4 0 7 5 2

3 1 7 4 6 0 2 5

3 1 7 5 0 2 4 6

3 5 0 4 1 7 2 6

3 5 7 1 6 0 2 4

3 5 7 2 0 6 4 1

3 6 0 7 4 1 5 2

3 6 2 7 1 4 0 5

3 6 4 1 5 0 2 7

3 6 4 2 0 5 7 1

3 7 0 2 5 1 6 4

3 7 0 4 6 1 5 2

3 7 4 2 0 6 1 5

4 0 3 5 7 1 6 2

4 0 7 3 1 6 2 5

4 0 7 5 2 6 1 3

4 1 3 5 7 2 0 6

4 1 3 6 2 7 5 0

4 1 5 0 6 3 7 2

4 1 7 0 3 6 2 5

4 2 0 5 7 1 3 6

4 2 0 6 1 7 5 3

4 2 7 3 6 0 5 1

4 6 0 2 7 5 3 1

4 6 0 3 1 7 5 2

4 6 1 3 7 0 2 5

4 6 1 5 2 0 3 7

4 6 1 5 2 0 7 3

4 6 3 0 2 7 5 1

4 7 3 0 2 5 1 6

4 7 3 0 6 1 5 2

5 0 4 1 7 2 6 3

5 1 6 0 2 4 7 3

5 1 6 0 3 7 4 2

5 2 0 6 4 7 1 3

5 2 0 7 3 1 6 4

5 2 0 7 4 1 3 6

5 2 4 6 0 3 1 7

5 2 4 7 0 3 1 6

5 2 6 1 3 7 0 4

5 2 6 1 7 4 0 3

5 2 6 3 0 7 1 4

5 3 0 4 7 1 6 2

5 3 1 7 4 6 0 2

5 3 6 0 2 4 1 7

5 3 6 0 7 1 4 2

5 7 1 3 0 6 4 2

6 0 2 7 5 3 1 4

6 1 3 0 7 4 2 5

6 1 5 2 0 3 7 4

6 2 0 5 7 4 1 3

6 2 7 1 4 0 5 3

6 3 1 4 7 0 2 5

6 3 1 7 5 0 2 4

6 4 2 0 5 7 1 3

7 1 3 0 6 4 2 5

7 1 4 2 0 6 3 5

7 2 0 5 1 4 6 3

7 3 0 2 5 1 6 4

  评论这张
 
阅读(1177)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018