首页 > 代码库 > 八皇后问题

八皇后问题

八皇后问题题解
这应该是典型的递归问题,当然也涉及枚举问题,回溯法;
首先对第一个皇后进行排序,第一列有8个位置供她选择,然后将其所在的行和两千对角线分别进行标记三个数
组中,在进行第n个皇后进行排序有八个位置供她选择,但要检验其所在行和对角线上是否已被其他皇后占领。
还有是一定要搞明白出战问题,在出战后要对标志进行变回原值。

输出是运用的小技巧很赞奥

 1 #include<stdio.h> 2 int a[16]={0},b[16]={0},c[16]={0}; 3 int q[8]; 4 int num=0; 5 void puts(int n) 6 { 7     int i,t; 8     printf("No. %d\n",n); 9     for(i=0;i<8;i++)10         {for(t=0;t<8;t++)11     {12         if(t==q[i])printf("Q ");13         else printf("* ");14     }15         printf("\n");16         }17 }18 void queen(int cur)19 {20     int i,t;21     if(cur==8){22         num++;23         puts(num);24     }25     else26     for(i=0;i<8;i++){27         if(a[i]==0&&b[i+cur]==0&&c[cur-i+8]==0)28     {29         q[cur]=i;30         a[i]=1;b[i+cur]=1;c[cur-i+8]=1;31         queen(cur+1);32         a[i]=0;b[i+cur]=0;c[cur-i+8]=0;33     }}34 }35 int main()36 {37     int t=0;38     queen(t);39     printf("%d",num);40     return 0;41 }

 

八皇后问题