subset.cpp

这是一个用满二叉树解决皇后问题的算法。

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

#define MAXNUM 40

//递归算法，用于得到长度为n的所有的0,1,…,m-1向量
void BacktrackRec(int);

//非递归算法，用于得到长度为n的所有的0,1,…,m-1向量
void BacktrackIter(void);

int  Partial(int);
void Output(void);

int X[MAXNUM+1];
int n;
int m;//满m叉树

long Allsolutions;//用于记录解的个数
long Allvertice;//用于记录结点的个数

void main(void)
{
   printf("please input n:\n");
   scanf("%d",&n);
   m=n;

   Allsolutions=0;
   Allvertice=1;

   //递归算法产生长度为n的所有的0,1,…,m-1向量
   BacktrackRec(1);

   //非递归算法产生长度为n的所有的0,1,…,m-1向量
   //BacktrackIter();

   printf("解的个数solutions=%ld\n",Allsolutions);
   printf("结点个数vertice=%ld\n",Allvertice);

   getch();
}

void BacktrackRec(int k)
{//递归算法.用于得到长度为n的所有的0,1,…,m-1向量
 //进入本次调用时X[1..k-1]已经固定
	for(int i=0;i<=m-1;i++)
	{
		X[k]=i;
		//如果满足剪枝条件就剪枝；否则深入搜索.例如，
		//if(Constrain(k)&&Bound(k))
		if(Partial(k))
		{     if(k==n)
		      {
			 Allsolutions++;
			 Output();
					 //exit(1);
		      }
		      else  BacktrackRec(k+1);
		}
	}
}


void Output(void)
{
	for(int i=1;i<=n;i++)
	   printf("%4d",X[i]+1);
	printf("\n");
}

void  BacktrackIter(void)
{//非递归算法，用于得到长度为n的所有的0,1,…,m-1向量

	int k;

	k=1;
	X[k]=-1;
	while(k>0)
	{
		while(X[k]<m-1)
		{
			X[k]++;
			//如果满足剪枝条件就剪枝；否则深入搜索.例如，
			//if(Constrain(k)&&Bound(k))
			if(Partial(k))
			{
				if(k==n)
				{
					Allsolutions++;    //统计解的个数
					Output(); //找到一个解即可输出
					//break;    //只找到一个解即可终止。
				}
				else {k++;X[k]=-1;}   //advance
			}
		 }
		 k--;     //backtrack
	}
}

//当求皇后问题的解时，用于在其m=n叉解树中剪枝.
int Partial(int k)
{
	//Allvertice++;//产生的结点个数，包括死结点。
	for(int i=1;i<k;i++)
		if((X[i]==X[k])||(abs(i-k)==abs(X[i]-X[k]))) return 0;

	Allvertice++;//产生的活结点个数，包括解结点。
	return 1;
}