bah.cpp

数据结构中的八皇后问题

#include<stdio.h>
#define  n  8   // n为皇后个数，m为摆法计数
int m=0,a[n]; // a[i]存放第i个皇后放置的行号,
int ok(int i, int j) //检查(i,j)上能否放棋子
{ int  j1=j;int i1=i;  int ok1=1;  //检查第i行上能否放棋子
  while( (j1>0)&&ok1)
       {j1--; ok1=(a[j1]!=i);}
   j1=j; i1=i;    //检查对角线上能否放棋子
  while( (j1>0)&&(i1>0)&&ok1) 
       {j1--; i1--; ok1=(a[j1]!=i1);} 
   j1=j; i1=i;     //检查另一对角线上能否放棋子
   while( (j1>0)&&(i1<n)&&ok1) 
         {j1--; i1++; ok1=(a[j1]!=i1) ;}
   return  ok1;
}

void queen(int j) //从第j列开始逐个试探
{   int j2=j;
	if (j2>n-1) 
      { m++;  printf("m=%d   ",m);
         for (int i=0;i<n;i++)  printf("    %d",a[i]);
         printf("\n");
       }    
   else  for(int i=0; i<n;i++)
             if(ok(i,j))  //检查(i,j)上能否放棋子
                { a[j]=i; //在(i,j)上放一个棋子
                   queen(j+1) ;
                 } 
}
void main()
{
	queen(0);
}