permutation.cpp

这是一个关于算法中的皇后问题的算法。

#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#define MAXNUM 40

void BacktrackRec(int);
void BacktrackIter(void);
int  Partial(int);

void Swap(int&,int&);
void Output(void);

int X[MAXNUM+1];
int n;
long Allsolutions;//用于记录解的个数
long Allvertice;//用于记录产生的结点个数

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

   Allsolutions=0;
   Allvertice=1;

   //递归算法产生1,2,…n所有排列
   for(int i=1;i<=n;i++)
	   X[i]=i;
   BacktrackRec(1);


   //非递归算法产生1,2,…n所有排列
   //for(int i=1;i<=n;i++)
   //	   X[i]=0;
   //BacktrackIter();

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

   getch();
}


void  BacktrackRec(int k)
{//递归算法.进入本次调用时X[1..k-1]已经固定。

	for(int i=k;i<=n;i++)
	{
		Swap(X[k],X[i]);
		//如果满足剪枝条件就剪枝；否则深入搜索.例如，
		if(Partial(k))
		{
			if(k==n)
			{	Allsolutions++;
				Output();
				//exit(0);
			}
			else	BacktrackRec(k+1);
		}
		Swap(X[k],X[i]);
	}
}

void Swap(int &a,int &b)
{
	int c;
	c=a;
	a=b;
	b=c;
}

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

void  BacktrackIter(void)
{//非递归算法.
	int k;

	k=1;
	X[k]=0;
	while(k>0)
	{
		while(X[k]<n)
		{
			X[k]++;
			if(Partial(k))
			{
			   if(k==n)
			   {
				Allsolutions++;    //记录解的个数
				Output(); //找到一个解即可输出
				//return;    //只找到一个解即可终止。
			   }
			   else  k++;         //advance
			}
		}
		X[k]=0;
		k--;                  //backtrack
	}
}

/*

//用于BacktrackIter()中产生所有的排列
int Partial(int k)
{
	//Allvertice++;//产生的结点个数(包括死结点)。
	for(int i=1;i<k;i++)
		if(X[i]==X[k]) return 0;

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


//用于BacktrackIter()中求皇后问题的解
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;
}

*/
//用于BacktrackRec(int)中求皇后问题的解
int Partial(int k)
{
	//Allvertice++;//产生的结点个数(包括死结点)。
	for(int i=1;i<k;i++)
		if(abs(i-k)==abs(X[i]-X[k])) return 0;

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