queenslv.c

拉斯维加斯随机算法+回溯算法实现国际象棋中的8皇后问题.

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

#define N  8
#define RUN_TIME	100

enum boolean {false,true};

int x[N+1]={0};
int y[N+1]={0};

int randomi(int m,int n)
{
  int j;
  if(m > n)
  {
    printf("n must large than m!!!\n");
    return -1;
  }
  if(m==n)
    return n;
//  srand((unsigned)time(NULL));
  while(1)
  {
    j = rand();
    j %= n;
    if(j < m)
        j += n-m;
    else
        return j;
  }
}

int place(int k)
{
 int j;
 for(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 i;
 if(t>N)
 {
   for(i=1;i<=N;i++)
     y[i]=x[i];
   return;
 }
 else
   for(i=1;i<=N;i++)
   {
    x[t]=i;
    if(place(t))
    {
      backtrack(t+1);
//      printf("in backtrace x[%d]=%d\n",t,x[t]); 
    }
   }
}

int QueensLV(int stopLV)
{
 int i,j,count=1,k=1;
 while((k <= stopLV) &&(count>0))
 {
   count=0;
   j=0;
   for(i=1;i<=N;i++)
   {
    x[k]=i;
    if(place(k))
    {
     count++;
     if(randomi(0,count)==0)
       j=i;
    }  
   }
   if(count>0)
     x[k++]=j;

//   for(i=1;i<k;i++)
//      printf("x[%d]=%d ",i,x[i]);
//   printf("\n(k) = %d\n",k);
 }
 if(count>0)
   return true;
 else
   return false;
}

int main(void)
{
  int i,stop,j=0,sucess=0;
  printf("Please input the integer to stopLV and start backtrack(<=%d):",N);
  scanf("%d",&stop);
  srand((unsigned)time(NULL));
  do{
     	if(stop<N)
  	{	
  		while(!QueensLV(stop))
   		;
     	}
	else
		QueensLV(stop);
  	backtrack(stop+1);
	if(y[N]!=0)
	{
		sucess++;
		printf("sucess = %d\n",sucess);
		for(i=0;i<=N;i++)
			y[i]=0;
	}
	j++;
	printf("j=%d\n",j);
  }while( j<RUN_TIME);
//  printf("\n%d Queens's problem,y[%d]=",N,N);
//  for(i=1;i<=N;i++)
//    printf("%d ",y[i]);
//  printf("\n");
    printf("Run %d times,success %d times!\n",RUN_TIME,sucess);

  return 0;
}