home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / progc / itcmar90.arj / QUEEN1.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-07  |  1.3 KB  |  59 lines
  1. /************************************************
  2. * QUEEN1 - the first attempt at solving the        *
  3. * queens problem.                                *
  4. *                                                *
  5. * INP:    c - the column # to place a queen in    *
  6. *        n - the maximum column (& row) number    *
  7. * USES:    Soln - updates this solution counter    *
  8. *        whenever a queen is successfully placed    *
  9. *        in the n'th column.                        *
  10. ************************************************/
  11.  
  12. #define TRUE   (1==1)    /* Boolean true value    */
  13. #define FALSE  (1==0)    /* Boolean false value    */
  14. #define MAXBRD 25        /* Maximum board size    */
  15.  
  16. void PrintBoard(int);
  17. void queens(int c, int n)
  18.     {
  19.     extern int  board[MAXBRD+1][MAXBRD+1];
  20.     extern long Solns;
  21.     int i,j,legal;
  22.  
  23.     /* Have we found a solution? */
  24.     if (c==n)
  25.         {
  26.         ++Solns;
  27.         return;
  28.         }
  29.  
  30.     /* Check each spot in the column */
  31.     for (i=0; i<n; i++)
  32.         {
  33.         legal=TRUE;     /* Legal until disproven*/
  34.         for (j=1; j<=c; j++)
  35.             {
  36.             /* Check row */
  37.             if (board[i][c-j] != 0)
  38.                 legal = FALSE;
  39.  
  40.             /* Check diagonal 1 */
  41.             if (i+j<n)
  42.                 if (board[i+j][c-j] != 0)
  43.                     legal = FALSE;
  44.  
  45.             /* Check diagonal 2 */
  46.             if (i-j>=0)
  47.                 if (board[i-j][c-j] != 0)
  48.                     legal = FALSE;
  49.             }
  50.         if (legal)
  51.             {
  52.             board[i][c]=1;    /* Put queen here    */
  53.             queens(c+1,n);    /* Process next col    */
  54.             board[i][c]=0;    /* Remove & try next*/
  55.             }
  56.         }
  57.     }
  58.  
  59.