queen_lv.cpp

采用LasVegas概率算法高效解决N皇后问题

#include <iostream.h>
#include <stdlib.h>


const int lenth=31;
const int T=10000;

int n;
int pr=0;
int time=0;
void Push(int i);
int Pop();
int tr[lenth];
int i,j,k,nb;


typedef struct conseq
{
	int totalSucc;   //成功时搜索的结点数
	int totalFail;   //失败时搜索的结点数
	int succ;        //成功的次数
}consequence;

consequence con[lenth];


int check(int k,int j)      //判断当前行k,列j是否为open位置
{
  int r;
  if(k==0&&j==0) return 1;
  for(r=0;r<k;r++)
  {
	  if(tr[r]==j) return 0;//列相同
	  if((r+tr[r])==(k+j)) return 0; //135度对角线
	  if((r-tr[r])==(k-j)) return 0;
  }
  return 1;
}

int uniform(int min,int max)
{
	return min+rand()%max;
}

bool backtrace(int k)
{
	int i,j,temp;
	pr=k;
	for(i=k,j=0;i<n;)
	{
		while(j<n)
		{
			if(check(i,j)) break;
			j++;
		}
		if(j<n)
		{
			Push(j);
			time++;
			i++;
			j=0;
		}
		else
		{
			i--;
			if(i==k-1) return false;  //保证不能搬动随机放置的皇后
			temp=Pop();
			j=temp+1;
		}
	}
	return true;
}

bool Queenlv(int StepVegas)
{
	
	k=0;
	if (StepVegas==0) 
	{
		if(backtrace(k)) return true;
		else return false;
	}
	do
	{
	nb=0;
	for(i=0;i<n;i++)
	{
		if(check(k,i))
		{
			nb=nb+1;
			if(uniform(1,nb)==1) j=i;
		}
	}
	if(nb>0)
	{
		tr[k]=j;
		time++;
		k++;
	}
	}while((nb!=0)&&(k!=StepVegas));

	if (nb>0) 
	{
		if(backtrace(k)) return true;
	}
	else return false;
	
}

void main()
{
	int times,count=0;
	double p,s,e,t;

	cout<<"Please input n"<<endl;
	cin>>n;
	for(int temp=0;temp<=n;temp++)
	{
		for(times=1;times<=10000;times++)
		{
			for(i=0;i<=lenth;i++)
		    	tr[i]=0;
			if(Queenlv(temp)) 
			{
				count++;
				con[temp].totalSucc+=time;

				time=0;
			}
			else
			{
				con[temp].totalFail +=time;
				time=0;
			}
		}
		con[temp].succ =count;
		count=0;
	}
	cout<<"i             p               s                e                  t"<<endl;
	for(i=0;i<=n;i++)
	{
		cout<<i<<"         ";
		p=double(con[i].succ)/T;
		s=double(con[i].totalSucc)/con[i].succ;
		if((T-con[i].succ)==0) 	e=0;
		else e=double(con[i].totalFail)/(T-con[i].succ);
		t=s+(1-p)*e/p;
		cout<<p<<"   "<<s<<"       "<<e<<"       "<<t<<"        "<<endl;
	}
}


void Push(int i)
{
	tr[pr++]=i;
}

int Pop()
{
	int temp;
	temp=tr[pr-1];
	pr--;
	return temp;
}