C 8 Queens

心得 :
只要知道如何判斷主,從對角線有沒有放皇后的方法,
還有注意同一行有沒有其他皇后,
之後就非常簡單!

以下是網路轉載...
经观察发现，对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7)
其主对角线（即左上至右下）上的每个点的i-j+7的值（范围在(0,14)）均相等；
其从对角线（即右上至左下）上的每个点的i+j的值（范围在(0,14)）均相等；
且每个主对角线之间的i-j+7的值均不同，每个从对角线之间的i-j+7的值亦不同；
如a[3][4]:
主：3-4+7=6
从：3+4=7
因此可设两个数组b[15],c[15]分别表示主、从对角线是否安全
（为1表示有皇后，不安全；为0表示安全）

http://aikosenoo.pixnet.net/blog/post/8249576  8皇后有詳細介紹
以上方法是轉載自網路的

#include <stdio.h>
#include <stdlib.h>

char *left_diag,*right_diag;
char *column_map,*queen_map;
int n;
int answer=0;
void print_queen()
{
  int i,j;
  for(i=1;i<=n;i++){
   for(j=1;j<=n;j++) 
    printf("%c",(*(queen_map+i)==j)?'Q':'*');
  printf("\n");  
  }
  printf("\n");

}
void queen(int x)
{
   int j;
   if(x>n){
       if(n!=0)  
          answer++;
       print_queen(); 
       }
   else{
      for(j=1;j<=n;j++){
          int R=x-j+8;
          int L=x+j;                            
        if(*(left_diag+L)&&*(right_diag+R)&&*(column_map+j)){                                             
         *(queen_map+x)=j;
         *(column_map+j)=*(left_diag+L)=*(right_diag+R)=0;
          queen(x+1);
         *(column_map+j)=*(left_diag+L)=*(right_diag+R)=1;
        }               
      }                     
     }  
}
int main()
{
  int i;
  printf("please input N :");
  scanf("%d",&n);
  left_diag = malloc(sizeof(int)*(n*2-1));
  right_diag = malloc(sizeof(int)*(n*2-1));
  column_map= malloc(sizeof(int)*(n+1));
  queen_map=malloc(sizeof(int)*(n+1));
 
  for(i=1;i<=n*2;i++)
    *(left_diag+i)=*(right_diag+i)=1;              
  for(i=1;i<=n;i++)
     *(column_map+i)=*(queen_map+i)=1;        
  queen(1);
  free(left_diag);
  free(right_diag);
  free(column_map);
  free(queen_map);
  printf("The Queen answer of %d is %d\n",n,answer);
  system("pause");
}