/*  问题描叙： 在一个矩阵中布局皇后使所有相邻的皇后既不在同一行 *  也不在同一列和同一对角线上。下面的是以前写的，死算，效率很低。 */ #include <stdio.h>#include <math.h>#include <mem.h> int test(int i,int j,int n,int *stack)     /* 检查位置是否合理 */{ int m,d;   for(m = 0; m < n; m ++) { d = *(stack + m);   if( d == -1)        continue;   else if(d == i || fabs(m - j) == fabs(i - d))    return 1; }  return 0;} void OutToScreen(int *matrix,int npos,int n){ int i,j;  printf("\nLayout:%d\n\n",npos);    for(i = 0; i < n; i ++) { for(j = 0; j < n; j ++)  { if( *(matrix + i*n + j) )   printf("%2c",1);      /* 头像 */    else  printf("%2c",219);   /* 小方格 */  }   printf("\n\n"); }}        /* 创建文件成功结果保存到磁盘 */void OutToDisk(int *matrix,int npos,int n,FILE **fp){ int i,j;  fprintf(*fp,"\nLayout:%d\n\n",npos);    for(i = 0; i < n; i ++) { for(j = 0; j < n; j ++)  { if( *(matrix + i*n + j) )   fprintf(*fp,"%2c",'@');          else  fprintf(*fp,"%2c",'*');     }   fprintf(*fp,"\n\n"); }} void main(){ int *matrix,*stack;  int n,npos = 0,i = 0,j = 0;  FILE *fp = 0;       /* 某些编译器没有定义NULL */   clrscr();  printf("\n\nEnter the number of empress(n > 1):");  scanf("%d",&n);  matrix = (int *)malloc(n * n * sizeof(int));    /* 分配内存区 */  stack = (int *)malloc(n * sizeof(int));  memset(matrix,0,n * n * sizeof(int));    /* 初始化 */  memset(stack,-1,n * sizeof(int));   fp = fopen("out.txt","w+");  if( !fp )       /* 创建文件成功同时将结果保存到文件 */  printf("\nCreat out.txt success,all result will also save to the file !");   while( 1 ) {   while( i < n)  { if( test(i,j,n,stack) )   i ++;    else { *(stack + j) = i;    /* 第j个皇后的位置 */    *(matrix + i*n + j) = 1; /* 该位置有皇后占领 */    break;         }  }   if( i == n)       /* 所有位置均不适合 */  { if(j == 0)   break;    /* 0 皇后没位置，搜索结束 */    else { *(stack + j) = -1;    /* 恢复初始值 */    j --;      /* 处理前一个皇后 */    i = *(stack + j);    *(matrix + i*n + j) = 0; /* 恢复初始值 */    i ++;     /* 搜索下一个位置 */         }  }        else if(j == n - 1)      /* 搜索到一种合理布局 */  { npos ++;    OutToScreen(matrix,npos,n);    if( fp )       OutToDisk(matrix,npos,n,&fp);    *(stack + j) = -1;    /* j皇后回到初始状态 */    *(matrix + i * n + j) = 0;    j --;  i = *(stack + j);      /* 改变前一个皇后的位置 */    *(matrix + i * n + j) = 0;    i ++;  }   else   { i = 0;  j ++;     /* 处理下一个皇后的位置 */  }       }  if(fp)  fclose(fp); free(matrix);   free(stack);     /* 释放内存空间 */}

评论