/*  问题描叙： 在一个矩阵中布局皇后使所有相邻的皇后既不在同一行
 *  也不在同一列和同一对角线上。下面的是以前写的，死算，效率很低。
 */

#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);     /* 释放内存空间 */
}

评论