八皇后算法

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使
其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
看了别人的代码自己的理解：
利用一维数组，采用递归回溯算法；
算法思想：（1）用i标记列，用board［i］标记行，在main中调用put_chess(0)在第一行任意选择一个点放一个皇后；
（2）让i循环，使board［n］＝i,调用判断函数；
（3）如果该次和前n-1次所选的点在一个＊字型结构（即board[i]==board[n]||(n-i)==abs(board[i]-board[n])，则返回（2）；否则（n!=8）        时递归调用put_chess(n+1);
（4）当n=7时，找到最后一个皇后所处的位置，此时满足n=8，打印出这一种摆法，这时根据递归函数的特点它将把n回溯到6，转到（3），以此类推；

源代码：
#include
#include
#define MAX 8
int board[MAX];

void show_result()
{       int i;  //列
for(i=0;i printf(”(%d,%d)”,i,board[i]);  //board[i] 行
printf(”\n”);
}

int check_cross(int n)
{
int i;
for(i=0;i {
if(board[i]==board[n]||(n-i)==abs(board[i]-board[n]))  //判断
return 1;
}
return 0;
}

void put_chess(int n)
{
int i;
for(i=0;i {
board[n]=i;
if(!check_cross(n))
{
if (n==MAX-1)
show_result();
else
put_chess(n+1);  //递归调用

}
}
}

void main()
{
put_chess(0);
}

算法2

#include
#include
#include
#include
#include "mytime.h"

#ifndef FALSE
# define FALSE 0
#endif
 
#ifndef TRUE
# define TRUE 1
#endif

#ifndef DEBUG
# define DEBUG 0
#endif

#define DEFAULT_SIZE 13

int sol_count = 0;  /* count of solutions to problem */
#pragma omp threadprivate (sol_count)


/*
 * contains array of queen positions.  Returns 1
 * if none of the queens conflict, and returns 0 otherwise.
 */
int ok(int n, char *a)
{
     int i, j;
     char p, q;

     for (i = 0; i < n; i++) {
      p = a[i];

      for (j = i + 1; j < n; j++) {
           q = a[j];
           if (q == p || q == p - (j - i) || q == p + (j - i))
            return 0;
      }
     }
     return 1;
}

/* fwd decl */
void nqueens(int n, int j, char *a);

/*
 * Extract out directives to prevent tid calls from affecting performance.
 */

int nqueens_taskq(int n) {
  int i;
  char *b, *a;
  int num_sol = 0;
 
  a = malloc(n * sizeof(char));
  b = malloc(sizeof(char));

  #pragma intel omp taskq private(i)
  {
    for (i = 0; i < n; i++) {
      #pragma intel omp task private(b)
      #pragma llc task_master_data (&i, 1)
      #pragma llc task_t_reduce_slave (&num_sol, int, 1, LLC_SUM)
      {
        sol_count = 0;
        b[0] = i;
        if (ok(1, b)) {
          nqueens(n, 1, b);
        }
        num_sol = sol_count;
      }
    }
  }
  return num_sol;
}

void nqueens_forall(int n) {
  int i;
  char *b, *a;
 
  sol_count = 0;
  a = malloc(n * sizeof(char));
  b = malloc(sizeof(char));

  #pragma omp parallel for reduction (+:sol_count)
  #pragma llc reduction_type (int)
  for (i = 0; i < n; i++) {
    b[0] = i;
    if (ok(1, b)) {
      nqueens(n, 1, b);
    }
  }
}


void nqueens_serial(int n) {
  int i;
  char *b, *a;

  a = malloc(n * sizeof(char));
  b = malloc(sizeof(char));
  sol_count = 0;

  for (i = 0; i < n; i++) {
    b[0] = i;
    if (ok(1, b)) {
      nqueens(n, 1, b);
    }
  }
}


/*
 * is an array of numbers.  The entries of contain
 * queen positions already set.  If there is any extension of
 * to a complete queen setting, puts one of these queen
 * settings (mallocted from the heap) in .  Counts all complete
 * solutions to the problem and updates .
 * Does not side-effect .
 */

char *sol = NULL;

void nqueens(int n, int j, char *a)
{
     if (n == j) {
    /* put good solution in heap. */
    #pragma omp critical
    {
          if( sol == NULL ) {
              sol = malloc(n * sizeof(char));
              memcpy(sol, a, n * sizeof(char));
          }
    }
    sol_count += 1;
     }

     /* try each possible position for queen */
     {
         int i;
         for (i = 0; i < n; i++) {
              /* mallocte a temporary array and copy into it */
              char* b = malloc((j + 1) * sizeof(char));
              memcpy(b, a, j * sizeof(char));
              b[j] = i;
              if (ok(j + 1, b)) {
                   nqueens(n, j + 1, b);
              }
         }
     }
}

int main(int argc, char *argv[]) {
  int size;
  int sol_iter, sol_forall, sol_taskq;
  CLOCK_TYPE chrono;
  double serial_time, forall_time, taskq_time;


  if (argc == 2) {
    size = atoi (argv[1]);
  }
  else {
    size = DEFAULT_SIZE;
  }


  LLC_printMaster( "Syntax: queens \n" );
  LLC_printMaster( "  board size:       %d\n", size );
  LLC_printMaster( "\n" ) ;

  CLOCK_Start(chrono);
  nqueens_serial(size);
  CLOCK_End(chrono, serial_time);
  sol_iter = sol_count;

  CLOCK_Start(chrono);
  nqueens_forall(size);
  CLOCK_End(chrono, forall_time);
  sol_forall = sol_count;

  CLOCK_Start(chrono);
  sol_taskq = nqueens_taskq(size);
  CLOCK_End(chrono, taskq_time);

  LLC_printMaster ("Solution (n = %d) -> serial = %d, forall = %d, taskq = %d\n",
       size, sol_iter, sol_forall, sol_taskq);

  LLC_printMaster ("%d\t%g\t#llc_plot0; n = %d, (t_seq=%g/t_forall=%g)\n",
            LLC_NUMPROCESSORS, (serial_time / forall_time), size, serial_time, forall_time);
  LLC_printMaster ("%d\t%g\t#llc_plot1; n = %d  (t_seq=%g/t_taskq=%g)\n",
            LLC_NUMPROCESSORS, (serial_time / taskq_time), size, serial_time, taskq_time);
  LLC_printMaster ("%d\t%g\t#llc_plot2; n = %d (t_forall=%g/t_taskq=%g)\n",
            LLC_NUMPROCESSORS, (forall_time / taskq_time), size, forall_time, taskq_time);
  return 0;

}