/* 

Faça uma função 

void cavalo (int n, int l, int c); 

que verifica se, partindo da posição (l,c) de um tabuleiro nxn, 
é possível, com n^2 - 1 pulos, cobrir todas as posições do 
tabuleiro. Neste caso, imprime a sequência de pulos.  

*/
#include <stdio.h>
#include <stdlib.h> 
#include "pilha.h"

int ** alocaMatriz (int lin, int col) {
  int ** mat = malloc (lin * sizeof(int *));
  int i;
  for (i = 0; i < lin; i++)
    mat[i] = malloc (col * sizeof(int));
  return (mat);
}

void liberaMatriz (int ** mat, int lin){
  int i;
  for (i = 0; i < lin; i++) free(mat[i]);
  free (mat);
}

void imprimeMatriz (int **a, int m, int n) {
    int i,j;
    for (i = 0; i < m; i++){
        for (j = 0; j < n; j++) printf("+---");
        printf("+\n");
        for (j = 0; j <n; j++)
          if(a[i][j] != 0) printf("|%3d", a[i][j]);
            else printf("|   ");
        printf("|\n");
    }
    for (j = 0; j < n; j++) printf("+---");
    printf("+\n");
}

puloCavalo proximo (puloCavalo atual) {
  puloCavalo prox;
  int px[9] = {0, -2, -1, 1, 2,  2,  1, -1, -2};
  int py[9] = {0,  1,  2, 2, 1, -1, -2, -2, -1};

  prox.lin = atual.lin + px[atual.mov];
  prox.col = atual.col + py[atual.mov];
  prox.mov = 1;
  return prox; 
} 

int puloValido (int ** tab, int n, puloCavalo x) {
  puloCavalo prox = proximo(x);
  if (prox.lin >= 0 && prox.col >= 0 && prox.lin < n
      && prox.col < n && tab[prox.lin][prox.col] == 0)
    return 1;
  return 0;
} 

void cavalo (int n, int lin, int col) {
  pilha *dec = criaPilha (n * n);
  puloCavalo atual; 
  int **tab = alocaMatriz (n, n);
  int i, j, ok, npulos;

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

  atual.lin = lin;
  atual.col = col;
  atual.mov = 1;
  npulos = 0;

  while (npulos < n * n - 1) {
    ok = 0;
    while (!ok && atual.mov <= 8){
      if (puloValido (tab, n, atual))
	ok = 1;
      else
	atual.mov++;
    } 
    if (ok) {
      npulos++;
      empilha (dec, atual);
      tab[atual.lin][atual.col] = npulos;
      atual = proximo(atual);
    }
    else { /* backtrack */
      if (pilhaVazia (dec)) {
	printf("Não tem passeio do cavalo :-(\n");
	liberaMatriz (tab, n);
	destroiPilha (dec);
	return;
      }
      atual = desempilha (dec);
      tab[atual.lin][atual.col] = 0;
      atual.mov++;
      npulos--;
    }
  }
  npulos++;
  tab[atual.lin][atual.col] = npulos; 
  
  imprimeMatriz (tab, n, n);
  liberaMatriz (tab, n);
  destroiPilha (dec); 
  
  return; 
} 


int main()
{
  int n, l, c; 
  printf("Entre n, linha e coluna iniciais:  "); 
  scanf("%d %d %d", &n, &l, &c); 
  cavalo(n, l, c); 
  return 0;
}