/*---------------------------------------------------------------------- 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 #include #include #include /*---------------------------------------------------------------------- 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() */