| /* |
| ** queens.c -- Find solutions to the Eight-Queens chess problem. |
| ** Roberto Sierra 3/19/84 Version 1.1 |
| ** |
| ** Description: |
| ** This program finds all the possible ways that N queens can |
| ** be placed on an NxN chessboard so that the queens cannot |
| ** capture one another -- that is, so that no rank, file or |
| ** diagonal is occupied by more than one queen. By default, |
| ** the program prints the first solution it finds. You can |
| ** use the -a option to print all solutions, or the -c option |
| ** just to count them. The program allows the chess board |
| ** to be from 1x1 (trivial case) to 100x100. Warning: the |
| ** larger the chess board, the longer it typically takes to |
| ** find each solution, even though there may be more of them. |
| ** |
| ** This is a terrific example of the utility of recursion. The |
| ** algorithm uses recursion to drastically limit the number |
| ** of board positions that are tested. The program is able |
| ** to find all 8x8 queen solutions in a fraction of a second |
| ** (not counting print time). The code makes no attempt to |
| ** eliminate symmetrical solutions, so the number of solutions |
| ** reported will always be higher than the actual number of |
| ** distinct solutions. |
| ** |
| ** |
| ** Usage: |
| ** queens [-ac] n |
| ** |
| ** n Number of queens (rows and columns). An integer from 1 to 100. |
| ** -a Find and print all solutions. |
| ** -c Count all solutions, but do not print them. |
| ** |
| ** The output is sent to stdout. All errors messages are |
| ** sent to stderr. If a problem arises, the return code is -1. |
| ** |
| ** |
| ** Examples: |
| ** |
| ** queens 8 ## Show an 8x8 solution |
| ** 8 queens on a 8x8 board... |
| ** Q - - - - - - - |
| ** - - - - Q - - - |
| ** - - - - - - - Q |
| ** - - - - - Q - - |
| ** - - Q - - - - - |
| ** - - - - - - Q - |
| ** - Q - - - - - - |
| ** - - - Q - - - - |
| ** |
| ** queens -c 8 ## Count all 8x8 solutions |
| ** 8 queens on a 8x8 board... |
| ** ...there are 92 solutions. |
| ** |
| ** queens -a 4 ## Show all 4x4 solutions |
| ** 4 queens on a 4x4 board... |
| ** |
| ** Solution #1: |
| ** - Q - - |
| ** - - - Q |
| ** Q - - - |
| ** - - Q - |
| ** |
| ** Solution #2: |
| ** - - Q - |
| ** Q - - - |
| ** - - - Q |
| ** - Q - - |
| ** |
| ** ...there are 2 solutions. |
| ** |
| ** |
| ** Build Instructions: |
| ** You'll need an ANSI C compiler (or the willingness to edit |
| ** the program a bit). If you've got Gnu C, then you can |
| ** compile and load the program as follows: |
| ** |
| ** gcc queens.c -ansi -o queens |
| ** |
| ** [If you're using MPW on the Mac, define '-d MPW' on the |
| ** compile line so that background processing will occur.] |
| ** |
| ** |
| ** Algorithm: |
| ** In a 1984 Byte article, I ran across an interesting letter |
| ** from a high school student who was attempting to solve the |
| ** Eight Queens problem using a BASIC interpreter. He had |
| ** developed a program which placed eight queens successively |
| ** on all sixty-four squares, testing for conflicts at each |
| ** iteration. Of course, such a program would require 64^8 |
| ** iterations (about 2.8x10^14 iterations). Even in C on a, |
| ** fast CPU, this could take months or years. Byte's answer was |
| ** to alter the loops so that the queens resided on separate |
| ** ranks, thereby reducing the number of iterations required |
| ** to find all solutions to 8^8 iterations (about 16 million). |
| ** More reasonable, but still requiring a chunk of CPU time. |
| ** |
| ** I puzzled about this problem a bit, and came to realize that |
| ** this was still wasting a lot of CPU cycles. Though I'm sure |
| ** others have come up with good algorithms, I decided to come |
| ** up with my own, with a particular eye on efficiency. The |
| ** resulting algorithm finds all 8x8 solutions in a fraction |
| ** of a second (there are 92 solutions, including rotations). |
| ** On a Sun 4, it'll find all 365,596 solutions on a 14x14 board |
| ** in a bit over 2 minutes (printing them out requires extra |
| ** time, of course). Even Byte's solution would require 14^14 |
| ** iterations (about 10^16) which would take aeons. |
| ** |
| ** My algorithm works as follows: |
| ** (1) Place a queen in the top left corner. |
| ** (2) Place another queen immediately below. |
| ** (3) Test for conflicts. If the second queen conflicts (it |
| ** does at first), then move it one square to the right. |
| ** (4) Loop step 3 until there are no conflicts. Place |
| ** the next queen on the board and recurse. |
| ** (5) If any queen reaches the right edge of the board, |
| ** remove it and 'pop' to the previous recursion level. |
| ** (6) Now repeat these steps recursively until all eight |
| ** queens (or however many) have been placed without |
| ** conflict -- the result is a solution to the problem, |
| ** which is counted and optionally printed. |
| ** |
| ** Because conflicts are tested as the recursion proceeds, |
| ** this has the effect of 'pruning' the recursion so that |
| ** a large number of board positions are not even attempted. |
| ** The result is that the algorithm runs in reasonable time. |
| ** |
| ** I used a few tricks to make the test-for-conflict code |
| ** extremely efficient -- there is no 'inner' loop to search |
| ** along ranks, files, or diagonals. A series of arrays are |
| ** maintained instead which indicate which queen currently |
| ** 'owns' each rank, file or diagonal. This makes the |
| ** algorithm really fly, though the code is a little hard to |
| ** read. Lastly, pointer arithmetic is used to reduce the |
| ** number of implicit multiplications used in array addressing. |
| ** |
| ** |
| ** Contact: |
| ** For queries regarding this program, contact Roberto Sierra |
| ** at any of the following addresses: |
| ** |
| ** Roberto Sierra |
| ** bert@netcom.com (preferred address) |
| ** 73557.2101@compuserve.com |
| ** |
| ** Tempered MicroDesigns |
| ** P.O. Box 170638 |
| ** San Francisco, CA 94117 |
| ** |
| ** |
| ** Fine Print: |
| ** This program is in the public domain and can be used for |
| ** any purpose whatsoever, including commercial application. |
| ** [I'd like to hear what you do with it, though.] |
| ** Absolutely no warranty or liability is implied or extended |
| ** by the author. |
| ** |
| ** |
| ** Modification History: |
| ** PRS 3/19/84 v1.0 -- Original version. |
| ** PRS 7/25/93 v1.1 -- ANSIfied the code. More efficient pointers. |
| */ |
| |
| |
| #include <stdio.h> /* Need standard I/O functions */ |
| #include <stdlib.h> /* Need exit() routine interface */ |
| #include <string.h> /* Need strcmp() interface */ |
| #ifdef MPW /* Macintosh MPW ONLY */ |
| # include <CursorCtl.h> /* Need cursor control interfaces */ |
| #endif |
| |
| #define MAXQUEENS 100 /* Max number of queens */ |
| #define MAXRANKS MAXQUEENS /* Max number of ranks (rows) */ |
| #define MAXFILES MAXQUEENS /* Max number of files (columns) */ |
| #define MAXDIAGS (MAXRANKS+MAXFILES-1) /* Max number of diagonals */ |
| #define EMPTY (MAXQUEENS+1) /* Marks unoccupied file or diagonal */ |
| |
| /* GLOBAL VARIABLES */ |
| |
| int queens; /* Number of queens to place */ |
| int ranks; /* Number of ranks (rows) */ |
| int files; /* Number of files (columns) */ |
| int printing = 1; /* TRUE if printing positions */ |
| int findall = 0; /* TRUE if finding all solutions */ |
| |
| unsigned long solutions = 0; /* Number of solutions found */ |
| int queen[MAXRANKS]; /* File on which each queen is located */ |
| int file[MAXFILES]; /* Which queen 'owns' each file */ |
| int fordiag[MAXDIAGS]; /* Which queen 'owns' forward diagonals */ |
| int bakdiag[MAXDIAGS]; /* Which queen 'owns' reverse diagonals */ |
| char *progname = NULL; /* The name of this program */ |
| |
| |
| /* -------------------------- PROTOTYPES ----------------------- */ |
| |
| void pboard(void); |
| void find(register int level); |
| |
| |
| /*-------------------------- main() ---------------------------- |
| ** MAIN program. The main purpose of this routine is to deal |
| ** with decoding the command line arguments, initializing the |
| ** various arrays, and starting the recursive search routine. |
| */ |
| int main(int argc, char **argv) |
| { |
| register int i; /* Loop variable */ |
| register char *p; /* Ptr to argument */ |
| char *usage = |
| "Usage: %s [-ac] n\n\ |
| \tn\tNumber of queens (rows and columns). An integer from 1 to 100.\n\ |
| \t-a\tFind and print all solutions.\n\ |
| \t-c\tCount all solutions, but do not print them.\n"; |
| |
| #ifdef MPW /* Macintosh MPW ONLY */ |
| InitCursorCtl(0); /* Enable cursor control */ |
| #endif |
| |
| progname = argv[0]; /* Name of the program */ |
| |
| /**** DECODE COMMAND LINE ARGUMENTS ****/ |
| printing = 0; |
| #ifdef SMALL_PROBLEM_SIZE |
| queens = 13; |
| #else |
| queens = 14; |
| #endif |
| findall = 1; |
| |
| for(i = 1; i < argc; ++i) { /* Scan through arguments */ |
| p = argv[i]; /* Ptr to base of argument */ |
| if(*p == '-') { /* Command line option? */ |
| while(*++p) { /* Loop through characters */ |
| switch(*p) { /* What is the character */ |
| case 'c': /* '-c' option */ |
| printing = 0; /* Counting, not printing */ |
| case 'a': /* '-a' option */ |
| findall = 1; /* Find all solutions */ |
| break; |
| default: /* Illegal option */ |
| fprintf(stderr,"%s: Illegal option '%s'\n",progname,argv[i]); |
| fprintf(stderr,usage,progname); |
| exit(-1); |
| } /* End of switch */ |
| } /* End of loop */ |
| } /* End of option test */ |
| else { |
| if(sscanf(p,"%d",&queens) != 1) { /* Read integer argument */ |
| fprintf(stderr,"%s: Non-integer argument '%s'\n",progname,p); |
| exit(-1); |
| } |
| if(queens <= 0) { /* N must be positive */ |
| fprintf(stderr,"%s: n must be positive integer\n",progname); |
| exit(-1); |
| } |
| if(queens > MAXQUEENS) { /* N can't be too large */ |
| fprintf(stderr,"%s: Can't have more than %d queens\n", |
| progname, MAXQUEENS); |
| exit(-1); |
| } |
| } /* End of argument test */ |
| } /* End of argument scan loop */ |
| if(!queens) { |
| fprintf(stderr,"%s: Missing n argument\n",progname); |
| fprintf(stderr,usage,progname); |
| exit(-1); |
| } |
| |
| ranks = files = queens; /* NxN board for N queens */ |
| printf("%d queen%s on a %dx%d board...\n", |
| queens, queens > 1 ? "s" : "", ranks, files); |
| fflush(stdout); |
| |
| /* Initialization */ |
| solutions = 0; /* No solutions yet */ |
| for(i = 0; i < MAXFILES; ++i) file[i] = EMPTY; |
| for(i = 0; i < MAXDIAGS; ++i) fordiag[i] = bakdiag[i] = EMPTY; |
| |
| /* Find all solutions (begin recursion) */ |
| find(0); |
| if(printing && solutions) putchar('\n'); |
| |
| /* Report results */ |
| if(solutions == 1) printf("...there is 1 solution\n"); |
| else printf("...there are %ld solutions\n", solutions); |
| |
| exit(0); /* No errors */ |
| } |
| |
| |
| /***********************/ |
| /**** ROUTINES ****/ |
| /***********************/ |
| |
| /*------------------------- pboard() --------------------------- |
| ** This routines prints the board for a particular solution. |
| ** The output is sent to stdout. |
| */ |
| void pboard(void) |
| { |
| register int i, j; /* Rank/File indices */ |
| |
| if(findall) /* Only if searching for all */ |
| printf("\nSolution #%lu:\n",solutions); /* Print solution number */ |
| |
| for(i = 0; i < ranks; ++i) { /* Loop through all ranks */ |
| for(j = 0; j < files; ++j) { /* Loop through all files */ |
| putchar(' '); /* Output a space */ |
| if(j == queen[i]) putchar('Q'); /* Output Q for queen... */ |
| else putchar('-'); /* or '-' if empty */ |
| } |
| putchar('\n'); /* Break line */ |
| } |
| fflush(stdout); /* Flush solution to output */ |
| } |
| |
| |
| /*-------------------------- find() ---------------------------- |
| ** FIND is the recursive heart of the program, and finds all |
| ** solutions given a set of level-1 fixed queen positions. |
| ** The routine moves a single queen through all files (columns) |
| ** at the current rank (recursion level). As the queen is moved, |
| ** conflict tests are made. If the queen can be placed without |
| ** conflict, then the routine recurses to the next level. When |
| ** all queens have been placed without conflict, a solution is |
| ** counted and reported. |
| */ |
| void find(register int level) |
| { |
| register int f; /* Indexes through files */ |
| register int *fp, *fdp, *bdp; /* Ptrs to file/diagonal entries */ |
| |
| #ifdef MPW /* Macintosh MPW ONLY */ |
| if(level & 7 == 0) /* Periodically break for... */ |
| SpinCursor(1); /* background processing */ |
| #endif |
| |
| if(level == queens) { /* Placed all queens? Stop. */ |
| ++solutions; /* This is a solution! */ |
| if(printing) pboard(); /* Print board if printing */ |
| if(!findall) exit(0); /* May stop after first solution */ |
| #ifdef MPW /* Macintosh MPW ONLY */ |
| SpinCursor(1); /* background processing */ |
| #endif |
| } |
| else { /* Not at final level yet */ |
| for( /* Move queen through all files */ |
| f = 0, /* Queen starts at left (file 0) */ |
| fp = file, /* Ptr to base of file array */ |
| fdp = &fordiag[level], /* Ptr to first fwd diag entry */ |
| bdp = &bakdiag[level+files-1] /* Ptr to first bak diag entry */ |
| ; |
| f < files /* Loop through all files */ |
| ; |
| ++f, /* Advance index */ |
| ++fp, ++fdp, --bdp /* Advance pointers */ |
| ) { |
| if(*fp >= level && /* No queen on the file? */ |
| *fdp >= level && *bdp >= level /* No queens on diagonals? */ |
| ) { |
| queen[level] = f; /* Note new position of queen */ |
| *fp = *fdp = *bdp = level; /* Place queen on file & diags */ |
| find(level+1); /* This level OK, recurse to next */ |
| *fp = *fdp = *bdp = EMPTY; /* Remove queen from file & diags */ |
| } /* End of conflict test */ |
| } /* End of file loop */ |
| } /* End if (level == queens) */ |
| } |
| |
| |
