首页 > 代码库 > 回溯4--八皇后问题
回溯4--八皇后问题
回溯4--八皇后问题
一、心得
二、题目及分析
皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
默认从每行开始摆，判断竖和两斜
八皇后问题：
这题的标记数组有三个
原数组数组没有
结果数组有
三、代码及结果
1 /* 2 默认从每行开始摆，判断竖和两斜 3 八皇后问题： 4 这题的标记数组有三个 5 原数组数组没有 6 结果数组有 7 */ 8 #include <iostream> 9 using namespace std; 10 int b1[100],b2[100],b3[100]; 11 //b1是竖 b2是正斜 b3是反斜 12 int ans[100]; 13 int total=0; 14 15 void print(){ 16 total++; 17 cout<<"<"<<total<<">"<<": "; 18 for(int i=1;i<=8;i++){ 19 cout<<ans[i]<<" "; 20 } 21 cout<<endl; 22 } 23 24 void search(int t){//t是轮数，也是行数 25 if(t==9) print(); 26 else 27 for(int i=1;i<=8;i++){ 28 if(b1[i]==0&&b2[t-i+16]==0&&b3[t+i]==0){ 29 ans[t]=i,b1[i]=1,b2[t-i+16]=1,b3[t+i]=1; 30 search(t+1); 31 b1[i]=0,b2[t-i+16]=0,b3[t+i]=0; 32 } 33 } 34 } 35 int main(){ 36 search(1); 37 cout<<total<<endl; 38 return 0; 39 }
回溯4--八皇后问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。