c语言编写的四皇后.c

人工智能学习中常见的四皇后问题的求解程序

/* 程序采用深都优先的算法*/
#include"stdlib.h"
#include"stdio.h"
#include"math.h"
#define NULL 0
#define TRUE 1
#define ERROR 0
#define N 6  /* 输入N的值可以控制执行的是几皇后问题 */


typedef struct SHH/* 定义的数据结构类型为链表型 */
 { int x;          /* x表示当前节点的行位置*/
   int y;           /* x表示当前节点的列位置*/
   struct SHH *father;/* 该指针指向上一行它的父生成节点*/
 }SHH,*TP;
 int Exam(int,int,TP);/*Exam函数的功能是每当生成新的节点时，调用该函数检验是*/
/*否跟它的父节点链有冲突现象*/
 void shuchu(TP);/* shuchu 函数的功能是当生成的节点已经到达第N行即最后一行*/
void Creates(int a,int b,TP *ip )/* Creates函数的功能是递归产生新的节点*/
 { int c=a,d=b;
   TP r;
  if((d>=(N+1))&&(c==1))/* 向上回朔到最后完成的出口处*/
 
    printf("the print is succeed");
  
   else
   {
       if(c>=(N+1))   /* 判断是否已经到达最后一行*/
			{shuchu(*ip);/* 调用shuchu 函数输出已经成功的情况的节点*/
	        (*ip)=(*ip)->father;
	         c=(*ip)->x;
	         d=(*ip)->y;

	         d=d+1;
	         
               (*ip)=(*ip)->father;
		        Creates(c,d,ip  );/* 向上回朔*/
	      }
	   else
	   {
	          if(Exam(c,d,*ip)) /*当生成新的节点时调用Exam 函数检验是否跟*/
/*父节点链有冲突*/
			  {     r=(TP)malloc(sizeof(SHH));/*当Exam返回真时，向下生成新的节点*/
                                  if(c==1)
								  { r->father=NULL;
	                   	  r->x=c;
	                   	  r->y=d;
		           	  (*ip)=r;
                       c=a+1;
					    d=1;
			   		   Creates(c,d,ip  );


					   }

                else /*当Exam返回假时，如果还未到达最后一行，将当前节点删去，*/
/*向右生成新的节点继续进行*/

		         	    { r->father=(*ip);
	                             r->x=a;
	                              r->y=b;
			    	       (*ip)=r;
						  c=a+1;
						  d=1;
			    	   Creates(c,d,ip );
				 	   }

             }
			  else
				   { if(b>=(N+1))

	           	     {

	            	 c=(*ip)->x;
	             	 d=(*ip)->y;
		     	     (*ip)=(*ip)->father;
					  d=d+1;
		     	     Creates(c,d,ip );

			 	    }



          	    else
			 	    Creates(c,d+1,ip );
		   	    }

		   	    }



   }

 }
 int Exam(int a,int b,TP t) /*每当生成新的节点时，调用该函数检验是*/
/*否跟它的父节点链有冲突现象*/
  { int c=1,d=1,flag=0;
    TP r=t;
    if(b<(N+1))
    {if(a==1&&b<(N+1))
     flag=1;
     else
	 {

        do

		{  c=r->x;
              d=r->y;
           if((a==c)||(b==d)||(abs(a-c)==abs(b-d)))/*检验是否在同一行或对角线有冲突情况*/
          break;
          else r=r->father;
	   } while(r!=NULL);


	  }

        if(r==NULL)
        flag=1;
	   if(flag==1)
		return(TRUE);
	      else 	return(ERROR);
	}
	
	else return(ERROR);
	 }

   




 void shuchu(TP s) /* shuchu 函数的功能是当生成的节点已经到达第N行即最后一行*/
/*时将其和父节点按回朔的方法打印在屏幕上*/
 {  TP r=s;
    
    int a[N];
	int  b[N];
	int i=0;
     do
     {    a[i]=r->x;
	      b[i]=r->y;
		  i++;
       r=r->father;
      }  while(r!=NULL);
	 for(i=N-1;i>=0;i--)
     printf("(%d,%d) ",a[i],b[i]);
	 printf("\n");
  }

main()
{   int a=1,b=1 ;
     TP r;

	 
     
      r=(TP)malloc(sizeof(SHH));
       r->x=a;
        r->x=b;
    r->father=NULL;
	 
     Creates(a,b,&r);/*将（1，1）节点传到Creates函数后递归调用，最后输出结果*/

}