#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define MAX_SIZE 21
#define True 1
#define False 0

int x[ MAX_SIZE ];

void nqueens( int );
int place( int );

void main( void )
{
   int n;

   for ( ; ; ) {
      printf( "\n\nnqueens: what size (greater than 20 to quit): " );
      scanf( "%d", &n );
      if ( n > 20 )
         exit( EXIT_SUCCESS );
      else
         nqueens( n );
   }
}

void nqueens( int n )
{
   int k, i;

   for ( k = 1, x[ 1 ] = 0; k > 0; ) {
      x[ k ]++;
      while ( x[ k ] <= n && !place( k ) )
         x[ k ]++;
      if ( x[ k ] <= n )
         if ( k == n ) {
            printf( "Solution:\n" );
            for ( i = 1; i <= n; i++ )
               printf( "\t%3d%3d\n", i, x[ i ] );
         }
         else {
            k++;
            x[ k ] = 0;
         }
      else
         k--;
   }
}

int place( int k )
{
   int i;

   for ( i = 1; i < k; i++ )
      if ( ( x[ k ] == x[ i ] ) ||
           ( abs( x[ k ] - x[ i ] ) == ( k - i ) ) )
         return False;
   return True;
}