#include <stdio.h>

int podecolocar (int i, int j, int coluna[]) {
  int k;
  for (k=0; k<i; k++) 
    if (j == coluna[k] || i-j == k-coluna[k] || i+j == k+coluna[j]) 
      return 0;
  return 1;
}

int coloca (int n, int coluna[]) {
  int i, j;

  coluna[0] = 0; 
  i = 1; 
  j = 0;
  while (i < n) 
    if (podecolocar(i,j,coluna)) {
      coluna[i] = j;
      i++; j=0;
    }
    else {
      j++;
      while (j == n) 
	if (i == 0)
	  return 0;
	else {
	  i--; 
	  j = coluna[i]+1;
	}
      /* Uma pequena otimização, que corta um pouco de simetria. */
      if (i == 0 && j >= (n+1)/2)
	return 0;
    }
  return 1;
}

main() {
  int n, *coluna, i;

  printf("Digite n: ");
  scanf("%d", &n);
  if ((coluna = (int *) malloc(n*sizeof(int))) == NULL) {
    printf("Erro na alocacao de memoria.\n");
    exit(0);
  }
  if (coloca(n, coluna)) {
    printf("A posicao das %d rainhas e':\n", n);
    for (i=0; i<n; i++) 
      printf("(%d,%d)\n", i, coluna[i]);
  }
  else 
    printf("Nao e' possivel colocar %d rainhas em um tabuleiro %dx%d.\n", n, n, n);
}