#include <iostream>
#include "Pilha.h"
using namespace std; 

bool podeColocar (int ** tab, int n, int l, int c)
{
  bool pode = true; 

  for (int i = 0; i < n; i++)
    if (tab[l][i] == 1 || tab[i][c] == 1)
      pode = false; 
  for (int i = 0; i < n; i++)
    if (c-l+i >= 0 && c-l+i < n)
      if (tab[i][c-l+i] == 1) 
	pode = false; 

  for (int i = 0; i < n; i++)
    if (c+l-i >= 0 && c+l-i < n)
      if (tab[i][c+l-i] == 1) 
	pode = false; 

  return (pode);
}

int main()
{
  Pilha<int> pos; 
  int atual = 0, col = 0, n;
  int **tab; 
  bool ok; 

  cout << "Digite n: ";
  cin >> n;
  
  tab = new int*[n];
  for (int i = 0; i < n; i++)
    tab[i] = new int[n];

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

  while (atual < n){
    ok = false; 
    while (col < n && !ok)
      if (podeColocar (tab, n, atual, col))
	ok = true; 
      else col++;
    if (ok){
      tab[atual][col] = 1; 
      pos.empilha(col);
      atual++;
      col = 0;
    }
    else {// Backtrack
      if (!pos.pilhaVazia()){
	col = pos.desempilha();
	atual--;
	tab[atual][col] = 0; 
	col++;
      }
      else break;
    }
  }
  if (atual == n){
    for (int i=0; i < n; i++){
      cout << "+";
      for (int j = 0; j < n; j++) cout << "-+"; 
      cout << endl << "|"; 
      for (int j=0; j <n; j++)
	if(tab[i][j] == 0)
	  cout << " |";
	else
	  cout << "*|";
      cout <<  endl; 
    }
    cout << "+";
    for (int j = 0; j < n; j++) cout << "-+"; 
    cout << "+" << endl; 
  }
  else 
    cout << "Não tem solução para " << n << endl;

  for (int i = 0; i < n; i++) delete [] tab[i];
  delete [] tab;
  return 0;
}