queenlv.c

来自「概率算法和回溯法结合」· C语言 代码 · 共 152 行

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>

/*check if the place (k,i) is safe*/
int isSafe(int k, int i, int *X)
{
 int j;

 j = 1;
 while(j < k){
    if(i == X[j] || abs(i - X[j]) == abs(k - j))
       return 0;
    j++;
 }
 return 1;
}

/*method of BackTrace to get one solution for N Queen problem,! line no. k must be lower than n*/
int BackTrace(int n, int k,int *X)
{
 int i;
 int j;

 j = k + 1;
 X[j] = 0; 
 while(j > k)
 { 
  X[j]=X[j]+1;
  while((X[j]<=n)&&(!isSafe(j, X[j], X)))
    X[j]=X[j]+1;
 
  if(X[j]<=n)/*the (j)th queen is safely placed on the place of (j, X[j]) */
   if(j==n)
     return 1;
   else{
     j = j + 1;
     X[j] = 0;
    }
   
  else j = j - 1;
 }
 return 0;
}

int QueenLV(int n, int stepVegas, int *X)
{
 int success = 0;
 int i, j, nb, k;
 
 if(stepVegas == 0)
     return BackTrace(n, 0, X);

 k = 0;/*k denotes line*/
 if(stepVegas > 0)
    do{
       nb = 0;
       for(i = 1; i <= n; i++){ /*i denotes column*/
          if(isSafe(k + 1, i, X) == 1){
          /* placing the (k+1)th queen on column i is safe*/
             nb++;
             if((rand() % nb + 1) == 1)
                j = i;
          }
       }
       printf("Column no.:%d\n", j);
       if(nb > 0){
          k++;
          X[k] = j;
       }
    }while(nb > 0 && k < stepVegas);

 if(nb > 0 && k < n)
    return BackTrace(n, k, X); 
 else if(nb > 0 && k == n)
    return 1;
 else
    return 0;
}

int* Obstinate(int n, int stepVegas)
{
 int success, *X, times = 0;

 X = (int *)malloc(n * sizeof(int));

 success = 0;
 do{
   success = QueenLV(n, stepVegas, X);
   times++;
   printf("Times:%d\n",times);
 }while(success != 1);
 return X;
}

int main(int argc, char *argv[])
{
 int i, n, *X, stepVegas, times;
 long usec_sum = 0, sec_sum = 0;
 double averg;
 struct rusage usage1, usage2;

 if(argc != 2){
    printf("Usage: %s n \n", argv[0]);
    exit(1);
 }
 n = atoi(argv[1]);
 if(n < 4){
    printf("the second must >= 4\n");
    exit(1);
 }
 do{
    printf("input the value of stepVegas(<=%d): ", n);
    scanf("%d", &stepVegas);
    if(stepVegas > n)
      printf("the value of stepVegas must <= %d\n", n);
 }while(stepVegas > n);
 printf("input the times to run successfully: ");
 scanf("%d", &times);

 srand((unsigned)time( NULL ));

 for(i = 0; i < times; i++){
    getrusage(RUSAGE_SELF, &usage1);
    X = Obstinate(n, stepVegas);
    getrusage(RUSAGE_SELF, &usage2);
    usec_sum = usec_sum + (usage2.ru_utime.tv_usec - usage1.ru_utime.tv_usec);
    sec_sum = sec_sum + (usage2.ru_utime.tv_sec - usage1.ru_utime.tv_sec) + usec_sum / 1000000L;
    usec_sum = usec_sum % 1000000L;
 }
 averg = ((double)sec_sum + ((double)usec_sum) / 1000000.00f) / times;
 printf("  Total run time: %lf seconds\n", averg*times);
 printf("Average run time: %lf seconds\n", averg);

 printf("\nOne solution: ");
 for(i = 1; i <= n; i++)
    printf("%d ", X[i]);
 free(X);
 printf("\n");
}