#include <stdio.h>
#include <stdio.h>
#include <memory.h>

int
extend_ok(int j, int k, char *a)
{
  int i;
  for (i = 0; i < k; i++)
    if (j == a[i] || j == a[i] - (k - i) || j == a[i] + (k - i))
      return 0;
  return 1;
}

int 
nqueens(int n, int k, char *a)
{
  if (n == k)
    return 1;
  else
    {
      int s = 0;
      int i;
      /* try each possible position for queen <k> */
      for (i = 0; i < n; i++) {
	if (extend_ok(i, k, a)){
	  /* allocate a temporary array and copy <a> into it */
	  char *b = alloca((k + 1) * sizeof(char));
	  memcpy(b, a, k * sizeof(char));
	  b[k] = i;	  
	  s += nqueens(n, k + 1, b);
	}
      }
      return s;
    }
}

int
main(int argc, char *argv[])
{
     int n, s;
     char *a;
     if (argc < 2) {
	  printf("%s: number of queens required\n", argv[0]);
	  return 1;
     }
     n = atoi(argv[1]);
     a = alloca(n * sizeof(char));

     printf("running queens %d\n", n);
     s = nqueens(n, 0, a);
     printf("%d answers\n", s);
     return 0;
}