lzh

刘政
posts - 17, comments - 1, trackbacks - 0, articles - 1

八皇后问题(回溯法)

Posted on 2010-08-22 21:19 lzh525 阅读(3006) 评论(0)  编辑 收藏 引用 所属分类: 数据结构及算法问题
1 /* 2 3 N皇后问题算法思想 4 5 由于这是一个平面上棋子布局处理问题,因此,我们可以将问题看成是一个二维数组问题。给八个皇后分别编号为1,2,…,8,其中第i个皇后放置在第i行上,并这就解决了不同皇后分别摆放在不同列的问题,这样又可以把问题简化为一个一维数组的问题,假设用一维数组arr来存放皇后所放置的列,对于第i个皇后,假设它存放在arr[i]列上,则对应的arr数组应满足如下的条件:[2] 6 (1) 因为一共只有8列,故a[i]的取值只能取1到8之间的数。 7 (2) 因为不同的皇后只能放在不同的列上,则对于任意的i和j,应满足如果i!=j,则a[i]!=a[j] 8 (3) 因为不同的皇后不能存放在同一对角线上,故连接两个皇后的直线的斜率应不能等于正负1,而连接任意第i个皇后和第j个皇后(i与j不同)的直线的斜率的计算公式为:(a[i]-a[j])/(i-j),即(a[i]-a[j])/(i-j)!=±1,即 9 |a[i]-a[j]|!=| i-j | 10 11 */ 12 #include<iostream> 13 #include<math.h> 14 using namespace std; 15 const MAX=1000; 16 long count; 17 bool is_a_solution(long k,long n) 18 { 19 return (k==n); 20 } 21 void process() 22 { 23 count++; 24 } 25 void construct_candidates(long *a,long k,long n,long *c,long &ncandidates) 26 { 27 long i,j; 28 bool legal_move;//是否为可选位置的标记 29 ncandidates=0;//可选位置的个数 30 for(i=1;i<=n;i++)//搜索第k行的皇后可选的范围(列) 31 { 32 legal_move=true; 33 for(j=1;j<k;j++)//第k行之前放置的皇后攻击的范围 34 { 35 if(abs(k-j)==abs(i-a[j])) //斜线攻击!!!第j行的皇后位置(j,a[j]),待放置的位置(k,i)(斜率为+-1) 36 legal_move=false; 37 else if(i==a[j]) //直线攻击! 38 legal_move=false; 39 } 40 if(legal_move==true) 41 { 42 c[ncandidates]=i;//第k行的皇后可放置在第k行的第i列 43 ncandidates=ncandidates+1; 44 } 45 } 46 } 47 void backtrack(long *a,long k,long n) 48 { 49 long c[MAX]; 50 long ncandidates; 51 long i; 52 if(is_a_solution(k,n)) 53 process(); 54 else 55 { 56 k++; 57 construct_candidates(a,k,n,c,ncandidates); 58 for(i=0;i<ncandidates;i++) 59 { 60 a[k]=c[i]; //k 从1 开始变起 61 backtrack(a,k,n); 62 } 63 } 64 } 65 int main() 66 { 67 long a[MAX],n; 68 while(cin>>n) 69 { 70 if(n==0) 71 break; 72 count=0; 73 backtrack(a,0,n); 74 cout<<"n="<<n<<" solution_count="<<count<<endl; 75 } 76 return 0; 77 } 78

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理