bhh.rar_八皇后递归_皇后问题

/*八皇后问题的递归算法*/ #include <stdio.h> #include <stdlib.h> #define N 8 /* 棋盘边长 */ #define XXN 15 /* 正（反）对角线个数 */ #define TRUE 1 #define FALSE 0 int map[N][N];/* 棋盘 */ int col[N]; /* 列 */ int XX[XXN]; /* 正对角线 */ int YY[XXN]; /* 反对角线 */ FILE* fp; int num=0; /* 解的个数 */ /** 显示一个解 */ void showMap() { int i,j; fprintf(fp,"\n--------------------------\n"); for(i=0;i<N;i++){ for(j=0;j<N;j++) fprintf(fp,"%-3d",map[i][j]); fprintf(fp,"\n"); } } /** 递归求解函数 */ int try(int y) { int i,j; int success=FALSE; if( y==N){ /* 求出一个解*/ showMap(); num++; return TRUE; } for(i=0;i<N;i++){ if(XX[N-y+i]==0 && YY[i+y]==0 && col[i]==0) /* 保证布局要求； 对角线，列，没有重复放置棋子 */ { XX[N-y+i]=YY[i+y]=col[i]=map[y][i]=1; if(try(y+1)) success=TRUE; /* 放下一个皇后 */ XX[N-y+i]=YY[i+y]=col[i]=map[y][i]=0; } } return success; } main() { int i,j,result; fp=fopen("queen8.txt","w+"); for(i=0;i<N;i++) for(j=0;j<N;j++) map[i][j]=0; for(i=0;i<XXN;i++) XX[i]=YY[i]=0; fprintf(fp,"\n start.............."); if(!try(0))printf("\n no resolution!"); fprintf(fp,"\n num=%d",num); }