nhuanghou ok.cpp

N皇后问题

#include <stdio.h>
//#include <stdlib.h>
#define MAXQ 100

int N, t;
int qx[MAXQ], qy[MAXQ];
int cure;
//char c;


int cheak(int x, int y)          //检测(x,y)处的皇后是否与已有皇后冲突，同列、同斜线均为冲突。
{
	if(y != 0)
	{
	 for(int i=0; i < cure; i++)
	 {
	 if((qx[i] == x) || (x - qx[i] == y - qy[i]) || (x - qx[i] == qy[i] - y))

	 return 0;
	 }
	}

	return 1;
}


	void Queen(void)
{ 
	int allfail;          //static  int allfail;
	cure=0; //已经放置的皇后数
	t=0; //解的个数
	for(int i=0; i < N; i++) //开始时，所有皇后全部不在棋盘上。
	qx[i]= -1;

    while( cure>= 0) //求出所有解，直到无法放置。
	{
	    allfail=1;                             //如果皇后不是在棋盘外(-1)，说明本次是回溯回来的。
        if(qx[cure] < N - 1)            //如果皇后已经处在最后一列，说明本皇后已经无法放置，这时再次回溯。
		{                                    //从上一次的皇后位置的下一位置开始寻找不冲突的位置。
	      for(int i=qx[cure] + 1; i < N; i++)
		 {
	       if(cheak(i, cure)) //如果不冲突，放置一个皇后
		   {
	         qx[cure]=i;
	         qy[cure]=cure;
	         cure++;
          	 allfail=0;
	         break;
		   }
		  }
		}

	     if(allfail)     //如果从上一次的皇后位置的下一位置开始全部冲突，则回溯。
		 {
	       qx[cure]= -1;   //将本皇后拿出棋盘。
	       cure--;
		  }

	     if(cure == N) //如果皇后数达到棋盘行(列)数，说明所有皇后都不冲突，输出解。
		{
	       ++t;
	       for(int i=0; i < N; i++)
		   {
			   if(i%N==0) 
	                 printf("\n第%d种摆法:\n",t);
	           for(int j=0; j < N; j++)
			   {
	              if(qx[i] == j)    
			           printf("Q ");
		          else     
			           printf("* ");
			   }
		       printf("\n");
              
		   }
           
		    /*   if(t%10==0)
			   {
                  printf("是否继续？(y/n):");
                  scanf("%c",&c);
                   if(c!='y') ;
                       exit(1);
				}*/

	       qx[cure]= -1;
	       cure--;
		}
	}
}


void main()
{   printf("Please input the number of the Queens:\nN=");
    scanf("%d",&N);
	
	if(N > MAXQ)
	    printf("Too big, N must less than 100.\n");
    
    Queen();
	printf("--------------------------------\n");
	printf("*********一共有%d种摆法*********\n", t);
	printf("--------------------------------\n");

}