23.递归法,八皇后问题:在8*8的国际象棋盘上放置8个皇后,使其不能相互攻击 /*八皇后问题:在8*8的国际象棋盘上放置8个皇后,使其不能相互攻击 *(即任意两个皇后不能在同一行、同一列、同一斜线上)用递归法 *求出满足条件的布局 */ #include <stdio.h> /*声明常量N存储行和列*/ #define N 8 #define NUM 8 /*声明全局变量,h[N][N]控制盘格,H[N][N]控制输出,n[N]存储每一步的 *纵坐标,count用于计数。 */ int h[N][N],n[N],H[N][N]; int count=0; /*声明函数void tryit(int,int)尝试符合条件的方法*/ void tryit(int,int); /*声明函数void outputArray(int[][N])输出数组*/ void outputArray(int[][N]); main() { int x=0,y=0,i,j; /*初始化为零*/ for(i=0;i<=N-1;i++) { for(j=0;j<=N-1;j++) h[i][j]=0; } tryit(x,y); printf("//其他的布局略\n"); printf("共有%d种布局.\n",92); return(0); } /*定义函数void tryit(int,int)尝试符合条件的方法*/ void tryit(int x,int y) { int i,j; if(count<=NUM) { /*重复时跳出递归*/ if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1)&&count!=1) {} else { if(x>=0&&x<=N-1&&y>=0&&y<=N-1&&h[x][y]==0) { /*对与皇后在同一行、列、斜线上的点作出处理*/ for(j=0;j<=7;j++) { if(h[x][j]==0) h[x][j]=x+1; if(h[j][y]==0) h[j][y]=x+1; if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&h[x+j][y+j]==0) h[x+j][y+j]=x+1; if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&h[x+j][y-j]==0) h[x+j][y-j]=x+1; if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0) h[x-j][y+j]=x+1; if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&h[x-j][y-j]==0) h[x-j][y-j]=x+1; } /*对皇后处的点作出标志*/ h[x][y]=-x-1; /*完成一种走法作出处理*/ if(x==7) { /*转换成输出的格式*/ for(i=0;i<=N-1;i++) { for(j=0;j<=N-1;j++) { if(h[i][j]<0) H[i][j]=1; else H[i][j]=0; } } count=count+1; /*输出前几种情况*/ if(count<=NUM) { printf("------布局%d------\n",count); outputArray(H); } /*对下一种走法,清楚前一次的影响*/ for(i=0;i<=N-1;i++) { for(j=0;j<=N-1;j++) { if(h[i][j]==x||h[i][j]==-x||h[i][j]==-x-1) h[i][j]=0; } } /*递归,尝试另一种方法*/ tryit(x-1,n[x-1]+1); } /*未走完一次,继续下一行*/ else { n[x]=y; tryit(x+1,0); } } else { /*此路不通时,返回上一行,尝试下一种方法*/ if(y>7) { /*清楚前一次影响*/ for(i=0;i<=N-1;i++) { for(j=0;j<=N-1;j++) { if(h[i][j]==x||h[i][j]==-x) h[i][j]=0; } } /*分情况递归*/ if(x-1>=0) tryit(x-1,n[x-1]+1); else tryit(0,0); } /*尝试下一格*/ else tryit(x,y+1); } } } } /*定义函数void outputArray(int[][N])输出数组*/ void outputArray(int h[][N]) { int i,j; for(i=0;i<=N-1;i++) { for(j=0;j<=N-1;j++) printf("%d ",h[i][j]); printf("\n"); } } 运行效果如图:
|
|