/*** solves the N-queen problem and prints all solutions ***/
/*** A.K. Hartmann May 2003                              ***/


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

/************************ queen() ********************/
/** Places a queen in different rows of column      **/
/** 'n' of checker board of size 'size'x'size'      **/
/** Calls itself recursively to search for          **/
/** solutions. If solution found, it is printed.    **/
/** PARAMETERS: (*)= return-paramter                **/
/**          n: current column                      **/
/**          N: size of board                       **/
/**     column: positions of queens                 **/
/**        row: is there a queen in row y?          **/
/**    diag_up: is there a queen in up diagonal ?   **/
/**  diag-down: is there a queen in down diagonal ? **/
/** RETURNS:                                        **/
/**    nothing                                      **/
/*****************************************************/
void queens(int n, int N, int *column, int *row, 
	   int *diag_up, int *diag_down)
{
  int t, t2;
  if(n == -1)                                        /* solution found ? */
  {
    for(t=0; t<N; t++)                              /* print solution */
    {
      for(t2=0; t2<column[t]; t2++)
	printf("*");
      printf("X");
      while((++t2)<N)
	printf("*");
      printf("\n");
    }
    printf("----------------------\n");
    return;
  }
  for(t=N-1; t>=0; t--)        /* place queen in all rows of column n */
  {
    if(!row[t]&&!diag_up[n-t+(N-1)]&&!diag_down[n+t])  /* can place ? */
    {
      row[t] = 1; diag_up[n-t+(N-1)] = 1; diag_down[n+t] = 1;
      column[n] = t;
      queens(n-1, N, column, row, diag_up, diag_down);
      row[t] = 0; diag_up[n-t+(N-1)] = 0; diag_down[n+t] = 0;      
    }
  }
  column[t] = 0;
}

int main(int argc, char *argv[])
{
  int N;                             /* size of checker board = parameter */
  int *column;                          /* position of a queen in the column */
  int *row;                          /* row[y] = is there a queen in row y ? */
  int *diag_up;         /* d[x-y+(N-1)] = a queen in diagonal x-y=const ? */
  int *diag_down;       /* d[x+y] = is there a queen in diagonal x+y=const ? */
  int t;                                                     /* loop counter */
  N = atoi(argv[1]);
  column = (int *) malloc(N*sizeof(int));
  row = (int *) malloc(N*sizeof(int));
  diag_up = (int *) malloc((2*N-1)*sizeof(int));
  diag_down = (int *) malloc((2*N-1)*sizeof(int));
  for(t=0; t<N; t++)                         /* initialise arrays = empty */
  {
    column[t] = 0; row[t] = 0;
  }
  for(t=0; t<2*N-1; t++)
  {
    diag_up[t] = 0; diag_down[t] = 0;
  }
  queens(N-1, N, column, row, diag_up, diag_down);
  free(row); free(column); free(diag_up); free(diag_down);
  return(0);
}