/* 
   Programa para resolver o problema de colocar n rainhas do jogo
   de xadrez num tabuleiro nXn sem que duas delas se ataquem  
*/
#include <stdio.h>
#include <stdlib.h>

char **alocamatriz(int m, int n);
void libera(char **tab, int m);
int colocarainhas(char **tab, int x, int y, int n);
int atacada(char **tab, int x, int y, int n);
void impressao(char **tab, int m, int n);

int main()
{
  int n, i, j;
  char **tab;

  printf("Tamanho do tabuleiro: ");
  scanf("%d",&n);
  tab = alocamatriz(n, n);
  if (tab == NULL){
    printf("Leitura nao pode ser feita\n");
    return 1;
  }

  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      tab[i][j] = ' ';

  if (colocarainhas(tab, 0, 0, n))
    impressao(tab,n,n);
  else
    printf("problema sem solucao\n");

  libera(tab,n);
  return 0;
}

void impressao(char **tab, int m, int n)
{
  int i, j;

  printf("\n");
  for (i = 0; i < m; i++){
    printf("  ");
    for (j = 0; j < n; j++)
      printf("|%c", tab[i][j]);
    printf("|\n");
  }
  printf("\n\n");
}

/* Tenta colocar as rainhas x, x+1, ..., n-1 nas linhas x, x+1, ..., n-1
 * a partir da posicao (x,y)
 * Devolve 1 se deu para colocar
 * Devolve 0 caso contrario
 */
int colocarainhas(char **tab, int x, int y, int n)
{
  /* coluna válida? */
  if (y == n)
    return 0;

  /* posição atacada? */
  if (atacada(tab,x,y,n))
    return colocarainhas(tab,x,y+1,n);

  tab[x][y] = 'R';

  /* última rainha? */
  if (x == n-1)
    return 1;

  /* Faltam rainhas... */
  if (colocarainhas(tab,x+1,0,n))
    return 1;

  /* Não deu. Vamos tentar próxima coluna */
  tab[x][y] = ' ';

  return colocarainhas(tab, x, y+1, n);

}

char **alocamatriz(int m, int n)
{
  char **tab;
  int i, j;

  tab = malloc(m*sizeof(char *));
  if (tab == NULL)
    return NULL;

  for (i = 0; i < m; i++){
    tab[i] = malloc(n*sizeof(char));
    if (tab[i] == NULL){
      for (j = 0; j < i; j++)
	free(tab[j]);
      free(tab);
      return NULL;
    }
  }

  return tab;
}

void libera(char **tab, int m)
{
  int i;

  for (i=0; i < m; i++)
    free(tab[i]);
  free(tab);
}

/* Verifica se a posicao (x,y) esta' atacada por alguma das rainhas colocadas nas
 * linhas 0, 1, .., x-1
 * Devolve 1 caso a posicao esteja atacada
 * Devolve 0 caso contrario
 */
int atacada(char **tab, int x, int y, int n)
{
  int i;

  /* Verifica coluna */
  for (i = 0; i < x; i++)
    if (tab[i][y] == 'R')
      return 1;

  /* Verifica uma diagonal */
  for (i = 0; x-i >= 0 && y-i >= 0; i++)
    if (tab[x-i][y-i] == 'R')
      return 1;

  /* Verifica outra diagonal */
  for (i = 0; x - i >= 0 && y+i < n; i++)
    if (tab[x-i][y+i] == 'R')
      return 1;

 return 0;
}