| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
|
| 公告 |
本站技术贴除标明为“原创”的之外，其余均为网上转载，文中我会尽量保留原作者姓名，若有侵权请与我联系，我将第一时间做出修改。谢谢！
——既瑜 |
| 统计 |
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1405641
建立时间:2005年3月12日 |
OICQ：215768265
njucs2001@hotmail.com
erichoo1982@gmail.com |
|
W3CHINA Blog首页 管理页面 写新日志 退出
 [【技术文档】]算法连载（4）--回溯法之N皇后问题[转载] |
1.问题描述：在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。
2.设计思想与分析： 基本思路：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。
#include <iostream.h>#include <math.h>
/*检查可不可以放置一个新的皇后*/bool place(int k, int *X){ int i; i=1; while(i<k) { if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k))) return false; i++; } return true;}/*求解问题的所有解*/void Nqueens(int n,int *X){ int k; X[1]=0;k=1; while(k>0) { X[k]=X[k]+1; while((X[k]<=n)&&(!place(k, X))) X[k]=X[k]+1; if(X[k]<=n) if(k==n) { for(int i=1;i<=n;i++) cout<<X[i]<<" "; cout<<"\n"; } else { k=k+1; X[k]=0; } else k=k-1; } }
void main(){ cout<<"|--------------N皇后问题--------------|"<<endl; cout<<"|---power by zhanjiantao(028054115)---|"<<endl; cout<<"|-------------------------------------|"<<endl<<endl; int n; int *X; int i; while(i) { cout<<"请输入皇后的个数:"; cin>>n; X=new int[n]; cout<<"问题的解有:"<<endl; Nqueens(n,X); cout<<"Press<1> to run again"<<endl; cout<<"Press<0> to exit"<<endl; cin>>i; } }
|
阅读全文(2881) | 回复(0) | 编辑 | 精华 |
|
