queens.c

遗传算法与回朔法对比 解决n皇后问题c源码

/*----------------------------------------------------------------------
  File    : queens.c
  Contents: Backtracking solution of the n queens problem
  Author  : Christian Borgelt
  History : 04.12.1998 file created
            09.01.1998 marking threatened fields simplified
            26.11.2000 memory allocation optimized
            23.10.2001 second search method added, option -a added
            09.01.2002 direct placement of queens added
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <assert.h>

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME     "queens"
#define DESCRIPTION "solve the n queens problem with backtracking"
#define VERSION     "version 1.4 (09.01.2002)         " \
                    "(c) 1998-2002   Christian Borgelt"

/* --- error codes --- */
#define OK            0        /* no error */
#define E_NONE        0        /* no error */
#define E_NOMEM     (-1)       /* not enough memory */
#define E_OPTION    (-2)       /* unknown option */
#define E_ARGCNT    (-3)       /* wrong number of arguments */
#define E_SIZE      (-4)       /* illegal chessboard size */
#define E_UNKNOWN   (-5)       /* unknown error */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static const char *errmsgs[] = {
  /* E_NONE      0 */  "no error\n",
  /* E_NOMEM    -1 */  "not enough memory\n",
  /* E_OPTION   -2 */  "unknown option -%c\n",
  /* E_ARGCNT   -3 */  "wrong number of arguments\n",
  /* E_SIZE     -4 */  "illegal chessboard size %d\n",
  /* E_UNKNOWN  -5 */  "unknown error\n" };

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
const char *prgname = NULL;    /* program name for error messages */
static int *qpos    = NULL;    /* positions of queens in rows */
static int **board  = NULL;    /* the chessboard */
static int size;               /* and its size */
static int all      = 0;       /* whether to find all solutions */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

void show1 (void)
{                              /* --- show a solution */
  int x, y;                    /* loop variables */

  for (y = size; --y >= 0; ) { /* traverse the rows of the board */
    for (x = 0; x < size; x++) /* traverse the fields of a row */
      printf((board[x][y] < 0) ? " Q" : " .");
    printf("\n");              /* print rows of the chessboard */
  }                            /* (empty fields: '.', Queens: 'Q') */
  printf("\n");                /* leave an empty line between sols. */
}  /* show1() */

/*--------------------------------------------------------------------*/

int search1 (int y)
{                              /* --- depth first search */
  int i;                       /* loop variable */
  int x, u, w;                 /* coordinates */
  int sol = 0;                 /* solution counter */

  if (y >= size) {             /* if a solution has been found, */
    show1(); return 1; }       /* show it and abort the function */
  for (x = 0; x < size; x++) { /* traverse fields of the row */
    if (board[x][y] != 0)      /* if the current field is */
      continue;                /* threatened, skip the field */
    board[x][y] = -1;          /* place the queen and */
    u = size-y; w = size-x;    /* set flags of threatened fields */
    for (i = u;                  --i > 0; ) board[x  ][y+i]++;
    for (i = (u <= x) ? u : x+1; --i > 0; ) board[x-i][y+i]++;
    for (i = (u <  w) ? u : w;   --i > 0; ) board[x+i][y+i]++;
    sol += search1(y+1);       /* search recursively */
    if (!all && (sol > 0)) break;
    for (i = u;                  --i > 0; ) board[x  ][y+i]--;
    for (i = (u <= x) ? u : x+1; --i > 0; ) board[x-i][y+i]--;
    for (i = (u <  w) ? u : w;   --i > 0; ) board[x+i][y+i]--;
    board[x][y] = 0;           /* remove the flags of the */
  }                            /* threatened fields and the queen */
  return sol;                  /* return the number of */
}  /* search1() */             /* solutions found */

/*--------------------------------------------------------------------*/

void show2 (void)
{                              /* --- show an individual */
  int x, y;                    /* loop variables */

  for (y = size; --y >= 0; ) { /* traverse the rows of the chessboard */
    for (x = 0; x < qpos[y]; x++) printf(" .");
    printf(" Q");
    while (++x < size) printf(" .");
    printf("\n");              /* print a row of the chessboard */
  }                            /* (empty fields: '.', Queen: 'Q') */
  printf("\n");                /* leave an empty line between sols. */
}  /* show2() */

/*--------------------------------------------------------------------*/

int search2 (int y)
{                              /* --- depth first search */
  int x, i, d;                 /* loop variables, buffer */
  int sol = 0;                 /* solution counter */

  if (y >= size) {             /* if a solution has been found, */
    show2(); return 1; }       /* show it and abort the function */
  for (x = 0; x < size; x++) { /* traverse fields of the current row */
    for (i = y; --i >= 0; ) {  /* traverse the preceding rows */
      d = abs(qpos[i] -x);     /* and check for collisions */
      if ((d == 0) || (d == y-i)) break;
    }                          /* if there is a colliding queen, */
    if (i >= 0) continue;      /* skip the current field */
    qpos[y] = x;               /* otherwise place the queen */
    sol += search2(y+1);       /* and search recursively */
    if (!all && (sol > 0)) break;
  }
  return sol;                  /* return the number of */
}  /* search2() */             /* solutions found */

/*--------------------------------------------------------------------*/

int place (int *qpos, int n)
{                              /* --- place the queens directly */
  int i, k;                    /* loop variable, buffer */

  if (n & 1) {                 /* for odd board size, place a queen */
    --n; qpos[n] = n; }        /* in the upper right corner */
  if (n == 2) return 0;        /* check for unsolvable problem */
  if (n % 6 != 2) {            /* if not 8, 14, 20, 26 etc. */
    for (i = k = n/2; --i >= 0; ) {
      qpos[i]   = --n;         /* two diagonal rows of queens */
      qpos[k+i] = --n;         /* (one in upper, one in lower half) */
    } }                        /* in knight move distance */
  else {                       /* for all other even field sizes */
    for (i = k = n/2; --i >= 0; ) {
      if ((k -= 2) <= 0) k += n;
      qpos[i]     = k-1;       /* a point symmetric structure with */
      qpos[n-i-1] = n-k;       /* four diagonal rows of queens */
    }                          /* in knight move distance */
  }
  show2();                     /* show the result */
  return 1;                    /* one solution found */
}  /* place() */

/*--------------------------------------------------------------------*/

static void error (int code, ...)
{                               /* --- print an error message */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  assert(prgname);              /* check the program name */
  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print the error message */
    va_end(args);               /* end argument evaluation */
  }
  exit(code);                   /* abort the program */
}  /* error() */

/*--------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main() */
  int  i, k = 0;                /* loop variables */
  char *s;                      /* to traverse the options */
  int  pos = 0;                 /* flag for position vector */
  int  dir = 0;                 /* flag for direct queens placement */
  int  *p;                      /* to traverse the chessboard */

  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print startup/usage message --- */
  if (argc > 1) {               /* if arguments are given */
    fprintf(stderr, "%s - %s\n", argv[0], DESCRIPTION);
    fprintf(stderr, VERSION); } /* print a startup message */
  else {                        /* if no argument is given */
    printf("usage: %s [options] n\n", argv[0]);
    printf("%s\n", DESCRIPTION);
    printf("%s\n", VERSION);
    printf("-a     find all solutions (default: find only one)\n");
    printf("-p     use a vector of positions instead of a board\n");
    printf("-d     place queens (no backtracking, one solution)\n");
    printf("n      number of queens/size of the chessboard\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */

  /* --- evaluate arguments --- */
  for (i = 1; i < argc; i++) {  /* traverse arguments */
    s = argv[i];                /* get option argument */
    if ((*s == '-') && *++s) {  /* -- if argument is an option */
      while (*s) {              /* traverse characters */
        switch (*s++) {         /* evaluate option */
          case 'a': all = 1;               break;
          case 'p': pos = 1;               break;
          case 'd': dir = 1;               break;
          default : error(E_OPTION, *--s); break;
        }                       /* set option variables */
      } }
    else {                      /* -- if argument is no option */
      switch (k++) {            /* evaluate non-option */
        case  0: size = atoi(s);  break;
        default: error(E_ARGCNT); break;
      }                         /* note fixed arguments */
    }
  }
  if (k != 1) error(E_ARGCNT);  /* check number of arguments and */
  if (size <= 0) error(E_SIZE, size);     /* the argument values */
  fprintf(stderr, "\n");        /* terminate the startup message */

  /* --- solve the problem --- */
  if (dir || pos) {             /* if to use a position vector */
    qpos = (int*)malloc(size *sizeof(int));
    if (!qpos) error(E_NOMEM);  /* create a vector of positions */
  }                             /* (one column index per row) */
  if (dir)                      /* if not to do backtracking, */
    i = place(qpos, size);      /* place the queens directly */
  else if (pos) {               /* if backtracking with pos. vector */
    i = search2(0); }           /* find and print solutions */
  else {                        /* if to use a full chessboard */
    board = (int**)malloc(size *sizeof(int*));
    if (!board) error(E_NOMEM); /* allocate a row vector */
    board[0] = p = (int*)calloc(size *size, sizeof(int));
    if (!p)     error(E_NOMEM); /* allocate the chessboard fields */
    for (i = 0; ++i < size; )   /* and organize them into rows */
      board[i] = p += size;
    i = search1(0);             /* find and print solutions */
  }
  if (i <= 0) printf("unsolvable\n");
  else        printf("%d solution(s)\n", i);

  return 0;                     /* return `ok' */
}  /* main() */