#include <stdio.h>

#define FALSE 0
#define TRUE  1

/* Eight Queens Solution   by     Paul Lefebvre

   Converted to C   6-28-92
   
   This program will find and display all 92 ways to place 8 queens on
   a chess board.
   
*/


main() {
             
   int i, rowchk[9], picked[9], diagsum[17], diagdif[16];
    
   /* Make sure all the arrays are correctly initialized */
   for ( i=1; i<9; i++ )
      rowchk[i] = picked[i] = 0;
        
   for ( i=2; i<17; i++ )
        diagsum[i] = FALSE;
        
   for ( i=0; i<16; i++ )
        diagdif[i] = FALSE;
        
   printf("Working ...\n\n");
   
        find_solutions( rowchk, diagsum, diagdif, picked );
        
   printf("\nThat's all folks!\n");
   return 0;  
}

void display_solution( picked, solnum )
   int picked[], *solnum;
/* This function will display the solution that was found. */
{
     int i, j;

     ++(*solnum);      /* Keep a running count of the solutions */
     printf("\n\n");

     /* This puts the actual chessboard on the screen */
     
     for ( i=1; i<=8; i++ ) {
         for ( j=1; j<=8; j++ ) 
            if ( picked[j] == i )
               printf("Q ");
            else
               printf("+ ");
         printf("\n");
     } 

     printf("That is solution number %d\n", *solnum);
} /* display_solution */

void back_up( row, col, rowchk, diagsum,
              diagdif, picked )
   int *row, *col, rowchk[], diagsum[], diagdif[], picked[];
/* This function allows the computer to 'back up' if it comes to a dead
   end.  The computer is moved back one column and the marking variables are
   set back to FALSE.  The row position is moved up by one so that the
   computer does not try the same position twice.  If the row position is
   already in the last one (8), then the function loops again to back up
   another column. */
{
     do {
         --(*col);
         if ( (*col) > 0 ) {
             *row = picked[*col];
             picked[*col] = 0;
             rowchk[*row] = FALSE;
             diagsum[(*col) + (*row)] = FALSE;
             diagdif[(*col) - (*row) + 7] = FALSE;
             if ( (*row) < 8 )
                 (*row)++;
             else
                 *row = 99;
         }
     }
     while  ( ((*col) > 0) && ((*row) > 8) );
} /* back_up */

void control_back_ups( row, col, rowchk, diagsum,
                       diagdif, picked, found, solnum )
   int *row, *col, rowchk[], diagsum[], diagdif[], picked[], *found, *solnum;
   
{
/* This is the function that determines if a solution has been found or
   if the computer is stuck and should back up. */

                         
   /* Solution found! */
   
   if ( (*col)==8 && *found ) {
      display_solution( picked, solnum );
      *found = FALSE;
      *col = 9;
      back_up( row, col, rowchk, diagsum, diagdif, picked );
   }
   else
      if ( (*row) > 8 )
         back_up( row, col, rowchk, diagsum, diagdif, picked );
} /* control_back_ups */

void find_solutions( rowchk, diagsum, diagdif,
                     picked )

   int rowchk[], diagsum[], diagdif[], picked[];
{
/* This is the function that does the actual checking for a correct solution.
   It will return to main only when all the solutions are found */
                        
   int found, done, start, solnum, row, col;
        
   start = 1;
   picked[1] = start;
   rowchk[start] = TRUE;
   diagsum[1+start] = TRUE;
   diagdif[1-start+7] = TRUE;
   done = FALSE;
   solnum = 0;
   col = 2;
   do {
      row = 1;
      do {
         found = FALSE;
         if ( col > 0 ) {
             if ( !rowchk[row] && !diagsum[col+row] &&
                  !diagdif[col-row+7] ) {
                 found = TRUE;
                 rowchk[row] = TRUE;
                 diagsum[col+row] = TRUE;
                 diagdif[col-row+7] = TRUE;
                 picked[col] = row;
              }
              else
                 row++;
              control_back_ups( &row, &col, rowchk, diagsum,
                                diagdif, picked, &found, &solnum );
          }
          else {
             found = TRUE;
             done = TRUE;
          }
      } while ( !found );
      col++;
   }while ( !done );
} /* find_solutions */