q.cpp

随机算法与回溯算法结合解N皇后问题.小程序,主要体现算法设计思想.

#include <stdlib.h>
#include <iostream.h>
#include <malloc.h>
#include <time.h>
#include <math.h>
#include <windows.h>

bool found = false;
int* x ;
int* ok ;

bool Place(int k)
{
	for(int j=1;j<k;j++)
		if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
			return false;
		return true;
}


void Backtrack(int t,int n)
{
	int i;
	if(t>n)
	{
		for(i=1;i<=n;i++)
			cout<<x[i]<<"   ";
		cout<<endl;
		found = true;
	}
	if(!found)
	{
		for(i=1;i<=n;i++)
		{
			x[t] = i;
			if(Place(t))
				Backtrack(t+1,n);
		}
	}
}


bool QueensLVB(int stopLV,int n)
{
	int k=1;
	int count=0;	
	srand( (unsigned)time( NULL ) );
	while(k<=stopLV)
	{
		for(int i=1;i<=n;i++)
		{
			x[k]=i;			
			if(Place(k))
				ok[++count]=i;				
		}
		if(count>0)
		{
			//srand( (unsigned)time( NULL ) );
			x[k++]=ok[rand()%count+1];
			count = 0;
		}
		else
			return false;	
	}
	 Backtrack(stopLV,n);	
	 return found;
}

void RepeatQueensLVB(int stopLV,int n)
{	
	while(!QueensLVB(stopLV,n));
}



void main(void)
{
	int stopLV;
	int n;
	//clock_t start, finish;  
	int start, finish; 
	double  duration;
	cout<<"Please input the Queen's number:";
	cin>>n;
	cout<<"Please input the stopLV:";
	cin>>stopLV;
	x =(int *)malloc((n+1)*sizeof(int));
	ok =(int *)malloc((n+1)*sizeof(int));
	cout<<"Program Running......"<<endl;
	//start=clock();
	start=GetTickCount();
	RepeatQueensLVB(stopLV,n);
	//finish=clock(); 
	finish=GetTickCount();
	duration = (double)(finish - start);
    cout<<"The time of Program is:"<<duration<<"ms"<<endl;
	free(x);
	free(ok);
}