/*  Algorithm 3.1 in Ruskey's textbook: Algorithm for the 8 queens problem. */

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

#define N 8

/* A, B, and C are boolean arrays.  A[i] == 1 iff row i is free,
i.e. has no queen in it.  B[i] and C[i] have likewise roles for the
SW-NE and NW-SE diagonals, respectively.  Note that A has precisely n
cells while B and C have precisely 2n - 1 cells each. */

int A[N]; int B[2*N-1]; int C[2*N-1];

/* sol is a natural numbers array.  At every successful moment in the
   backtracking it represents a permutation of the numbers 1 .. N. */

int sol[N];

void Print() {
  int i;

  /* printf("\n"); */
  for (i=0; i < N ; i ++)  printf(" %2d", sol[i] + 1);

  printf("\n");
}

void Q(int col) {
  int row;

  for (row=0; row < N; row ++) {
    
    /* Check if the current <row,col> pair refers to a cell that is
       free.  It is obvious that there is no queen in column "col" so
       it suffices to make sure there is no queen in row "row" and in
       both diagonals that contain <row,col>. */
    if (A[row] && B[row + col] && C[row - col + (N-1)]) {
      /* OK, <row,col> is free. */

      /* place a queen in <row, col>. */
      sol[col] = row;

      /* declare row "row" as occupied and ditto for the row+col SW-NE
	 diagonal and for the row-col+(N-1) NW-SE diagonal. */
      A[row] = 0;
      B[row + col] = 0;
      C[row - col +(N-1)] = 0;

      /* Check whether we are at the bottom of the recursion. */
      if (col < N-1)
	/* No, there are more columns to place queens in. */
	Q(col+1);
      else
	/* Yes, we are done for the moment.  The sol array represents
	   a valid placement of N queens on an NxN board. */
	Print();

      /* declare row "row" as free and ditto for the row+col SW-NE
	 diagonal and for the row-col+(N-1) NW-SE diagonal. */
      A[row] = 1;
      B[row + col] = 1;
      C[row - col +(N-1)] = 1;
      }
  }
}

int main() {
  int i;

  /* declare all row and diag positions free */
  for (i=0; i < N; i ++) A[i] = 1;
  for (i=0; i < 2*N-1; i ++) {B[i] = 1; C[i] = 1;}
  
  Q(0);

  return 0;
}