/* 

Faça uma função 

int nRainhas(int tab[MAX][MAX], int n, int lin);

que devolve 1 se é possível colocar n rainhas num tabuleiro n x n 
começando na rainha na linha lin; e 0 caso contrário. 

A matriz tab terá zero nas posições livres e 1 nas posições ocupadas pelas 
rainhas

*/ 

#include<stdio.h> 
#define MAX 400

int posicaoLivre (int tab[MAX][MAX], int n, int lin, int col);
void imprimeTab (int tab[MAX][MAX], int n); 
int nRainhas (int tab[MAX][MAX], int n, int atual); 

void imprimeTab (int a[MAX][MAX], int n)
{
    int i,j;
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++) printf("+-");
        printf("+\n");
        for (j = 0; j <n; j++)
            if(a[i][j] == 1) printf("|R");
            else printf("| ");
        printf("|\n");
    }
    for (j = 0; j < n; j++) printf("+-");
    printf("+\n");
}


int posicaoLivre( int tab[MAX][MAX], int n, int lin, int col)
{
  int livre = 1, i, j; 
  /* verifica linha e coluna */
  for (i = 0; i < n; i++)
    if (tab[lin][i] == 1 || tab[i][col] == 1)
      livre = 0; 

  /* verifica as duas diagonais */
  for (i = 0; i < lin; i++){
    j = (col - lin) + i;
    if (j >= 0 && tab[i][j] == 1)
      livre = 0; 
    j = (col + lin) - i; 
    if (j < n && tab[i][j] == 1)
      livre = 0;
  } 
  return livre;
} 


int nRainhas(int tab[MAX][MAX], int n, int lin)
{
  int col, deucerto = 1; 

  if (lin < n){
    deucerto = 0; 
    for (col = 0; col < n && deucerto == 0; col++){
      if (posicaoLivre (tab, n, lin, col) == 1){
	tab[lin][col] = 1; 
	deucerto = nRainhas (tab, n, lin + 1); 
        if (deucerto == 0){
	  tab[lin][col] = 0; 
	} 
      } 
    } 
  } 
  return (deucerto); 
} 

int main()
{
  int tab[MAX][MAX], n, i, j; 

  printf("Digite n > 0: ");
  scanf ("%d", &n); 

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

  if (nRainhas (tab, n, 0) == 1){
    imprimeTab(tab, n); 
  } 
  else{
    printf("Nao tem solucao para %d\n", n);
  } 
  return 0; 
}