/*
	Alunos: Mateus Mendelson Esteves da Silva e Amadeu Medina Borges
	Matrículas: 11/0017579 e 10/0024157
	Data de entrega: 06/11/2011
	Estruturas de Dados, Turma E, Professor Díbio, 2º/2011
*/
#include <stdlib.h>
#include <stdio.h>

/* Estruturas */
struct no{ //Estrutura para a árvore genérica (nó)
       int info;
       int lin;//Indica a linha no tabuleiro
       int col;//Indica a coluna no tabuleiro
       struct no *cima;//quadrado de cima
       struct no *baixo;//quadrado de baixo
       struct no *direita;//quadrado da direita
       struct no *esquerda;//quadrado da esquerda     no tabuleiro
};
typedef struct no No;//No quer dizer Nó

////////////////////////////////

/* Protótipos das funções */
void libera_tabuleiro(int **, int);

void imprime_tabuleiro(int **, int);

void preenche_arvore_de_possibilidades(No *, int **, int, int *);

No *cria_no(int, int, int, No *, No *, No *, No *);

void libera_arvore_de_jogos(No *);

int buscar_o_no_final(No *, int , int **, int);

///////////////////////////////////////////////////////////

/* Função principal */
int main(){
    FILE *fonte, *resultado;
    int **tabuleiro;//'Alterar' indicará as posições que podem ser alteradas com 0. As que não podem, com 1
    int x = 0;
    int *confirmacao = &x;//Confirma se o tabuleiro tem solução( 0 quer dizer sem solução;  != 0 significa tem solução
    int N, i, j;
    int ii = -1, ji = -1; //Posição incial, ou seja, coordenada do número 1. (ii = linha incial; ji = coluna inicial)
    No *r;//Raíz da árvore genérica (árvore de jogo). Ela será formada por todas as possibilidades de jogo.

    fonte = fopen("entradaProj4.txt", "r");

    if(fonte == NULL){
             printf("Arquivo fonte nao encontrado!\n\n");
             //system("PAUSE");
             exit(1);
    }

    fscanf(fonte, "%d", &N);

    if(N < 6 || N > 10){
         printf("\n\nErro! O arquivo de entrada designa um tabuleiro ");
         if(N <= 6){
              printf("menor do que o minimo permitido!\n\n");
         }else{
                    printf("maior do que o maximo permitido!\n\n");
         }
         fclose(fonte);//Fechando o arquivo fonte
         //system("PAUSE");
         exit(2);
    }

    //Iniciando e preenchendo o tabuleiro
    tabuleiro = (int **) malloc(N*sizeof(int));

    for(i = 0; i < N; i++){
          tabuleiro[i] = (int *) malloc(N*sizeof(int));
    }

    //Preenchendo o tabuleiro
    for(i = 0; i < N; i++){
          for(j = 0; j < N; j++){
                fscanf(fonte, "%d", &tabuleiro[i][j]);
          }
    }

    //Fechando o arquivo fonte
    fclose(fonte);

    //Imprimindo o tabuleiro inicial
    printf("Tabuleiro inicial:\n\n");
    imprime_tabuleiro(tabuleiro, N);
    printf("\n");

    //Buscando a posição inicial
    for(i = 0; i < N; i++){
          for(j = 0; j < N; j++){
                if(tabuleiro[i][j] == 1){
                                   ii = i;
                                   ji = j;
                }
          }
    }

    if(ii == -1){
          printf("\n\nErro! O tabuleiro nao possue posicao inicial! Encerrado!\n\n");
          //system("PAUSE");
          exit(3);
    }

    r = cria_no(1, ii, ji, NULL, NULL, NULL, NULL);//Criando a raiz da árvore

    preenche_arvore_de_possibilidades(r, tabuleiro, N, confirmacao);//Preenche a árvore r, que se refere à jogadas de "tabuleiro" que possui N*N posições

    if(*confirmacao == 0){
                    printf("\nO tabuleiro nao possui solucao!\n\n");

                    //Liberando estruturas
                    libera_arvore_de_jogos(r);
                    libera_tabuleiro(tabuleiro, N);
                    free(confirmacao);

                    //system("PAUSE");
                    exit(4);
    }

    x = buscar_o_no_final(r, N, tabuleiro, 0);

    //Imprimindo a solução do tabuleiro
    printf("\nSolução:\n\n");
    imprime_tabuleiro(tabuleiro, N);
    printf("\n");

    //Salvando a solução no arquivo de texto
    resultado = fopen("solucaoProj4.txt", "w");//Criando o arquivo

    for(i = 0; i < N; i++){
          for(j = 0; j < N; j++){
                fprintf(resultado, "%d ", tabuleiro[i][j]);
          }
          printf("\n");
    }

    //Fechando o arquivo
    fclose(resultado);

    //Liberando estruturas
    libera_arvore_de_jogos(r);
    libera_tabuleiro(tabuleiro, N);
    free(confirmacao);

    //system("PAUSE");
    return 0;
}
////////////////////////////////////////////////////////////////

//Corpo das funções

//Função que imprime o tabuleiro
void imprime_tabuleiro(int **tabuleiro, int t){
     int i, j;

     for(i = 0; i < t; i++){
          for(j = 0; j < t; j++){
                printf("%d ", tabuleiro[i][j]);
          }
          printf("\n");
    }
}

//Função que libera o tabuleiro
void libera_tabuleiro(int **p, int t){
     int i;

     for(i = 0; i < t; i++){
           free(p[i]); //Liberando as linhas da matriz
     }
     free(p); //Liberando a matriz
}

//Função que libera a árvore de jogo
void libera_arvore_de_jogos(No *arvore_jogo){
     No *p = arvore_jogo;

     if(p->cima == NULL && p->baixo == NULL && p->direita == NULL && p->esquerda == NULL){
                free(p);
     }else if(p->cima != NULL){
           libera_arvore_de_jogos(p->cima);
     }else if(p->baixo != NULL){
           libera_arvore_de_jogos(p->baixo);
     }else if(p->direita != NULL){
           libera_arvore_de_jogos(p->direita);
     }else if(p->esquerda != NULL){
           libera_arvore_de_jogos(p->esquerda);
     }
}



void preenche_arvore_de_possibilidades(No *r, int **tabuleiro, int N, int *confirmacao){ //Já que a posição inicial já é fornecida (de acordo com o roteiro do projeto) não nos preocuparemos com os casos em que o tabuleiro inicial não possui o número 1 (que é a posição inicial)
   int i = r->lin, j = r->col;
   int apoio;
   int x;

   if(r->info == N*N){
              x = r->info;//Checagem para saber se o último número foi colocado no tabuleiro, ou seja, se há solução
              *confirmacao = x;
   }

   if(r->info < N*N && r != NULL){//Checa se já preenchemos a árvore com todos os números e se o nó é um nó terminal (ou inválido)

             if((j + 1 < N) && tabuleiro[i][j + 1] == 0 || tabuleiro[i][j + 1] == (r->info) + 1){
                                r->direita = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i, j + 1, NULL, NULL, NULL, NULL);

                                apoio = tabuleiro[i][j + 1];//Armazenamos o valor inicial nessa coordenada
                                tabuleiro[i][j + 1] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
                                //printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
                                //system("PAUSE");
                                preenche_arvore_de_possibilidades(r->direita, tabuleiro, N, confirmacao);

                                tabuleiro[i][j + 1] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
             }
             if((j - 1 >= 0) && (tabuleiro[i][j - 1] == 0 || tabuleiro[i][j - 1] == (r->info) + 1)){
                                if(j + 1 < N && tabuleiro[i][j + 1] == (r->info) + 1){//Só há um caminho possível
                                }else{
                                      r->esquerda = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i, j - 1, NULL, NULL, NULL, NULL);

                                      apoio = tabuleiro[i][j - 1];//Armazenamos o valor inicial nessa coordenada coordenada
                                      tabuleiro[i][j - 1] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
                                      //printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
                                      //system("PAUSE");
                                      preenche_arvore_de_possibilidades(r->esquerda, tabuleiro, N, confirmacao);

                                      tabuleiro[i][j - 1] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
                                }
             }
             if((i + 1 < N) && (tabuleiro[i + 1][j] == 0 || tabuleiro[i + 1][j] == (r->info) + 1)){
                             if((j + 1 < N && tabuleiro[i][j + 1] == (r->info) + 1) || (j - 1 >= 0 && tabuleiro[i][j - 1] == (r->info) + 1)){//Só há um caminho possível
                             }else{
                                   r->baixo = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i + 1, j, NULL, NULL, NULL, NULL);

                                   apoio = tabuleiro[i + 1][j];//Armazenamos o valor inicial nessa coordenada coordenada
                                   tabuleiro[i + 1][j] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
                                   //printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
                                   //system("PAUSE");
                                   preenche_arvore_de_possibilidades(r->baixo, tabuleiro, N, confirmacao);

                                   tabuleiro[i + 1][j] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
                             }
             }
             if((i - 1 >= 0) && (tabuleiro[i - 1][j] == 0 || tabuleiro[i - 1][j] == (r->info) + 1)){
                             if((j + 1 < N && tabuleiro[i][j + 1] == (r->info) + 1) ||(j - 1 >= 0 && tabuleiro[i][j - 1] == (r->info) + 1) || (i + 1 < N && tabuleiro[i + 1][j] == (r->info) + 1)){//Só há um caminho possível
                             }else{
                                   r->cima = cria_no((r->info) + 1 /* número seguinte no tabuleiro */, i - 1, j, NULL, NULL, NULL, NULL);

                                   apoio = tabuleiro[i - 1][j];//Armazenamos o valor inicial nessa coordenada coordenada
                                   tabuleiro[i - 1][j] = (r->info) + 1;//Alteramos temporariamente o valor nessa coordenada, para evitar que utilizemos duas vezes o mesmo quadrado na montagem da árvore
                                   //printf("\n%d\t%d\t%d\n", r->info, r->lin, r->col);
                                   //system("PAUSE");
                                   preenche_arvore_de_possibilidades(r->cima, tabuleiro, N, confirmacao);

                                   tabuleiro[i - 1][j] = apoio;//Recolocamos o valor original na posição do tabuleiro, para que nada seja alterado ao final
                             }
             }
             //A última condição dos laços acima (if) serve para verificar se o ponto pertence ao tabuleiro
   }
}

//Função que apenas cria um nó
No *cria_no(int numero /*Informação a ser armazenada no nó*/, int i/*linha da informação*/, int j /*Coluna da informaçao*/, No *Cima, No *Baixo, No *Direita, No *Esquerda){//4 últimos argumentos: indicam os nós que serão ligados ao novo nó
                No *p;

                p = malloc(sizeof(No)); //Criando o nó

                //Preenchendo o nó com as informações
                p->info = numero;
                p->lin = i;
                p->col = j;
                p->cima = Cima;
                p->baixo = Baixo;
                p->direita = Direita;
                p->esquerda = Esquerda;

                return p; //Retornando o nó
}
 //Função que busca a solução correta na árvore e preenche o tabuleiro
int buscar_o_no_final(No *r, int N, int **tabuleiro, int x){

      if(x == 0){//Indica que ainda não encontramos o nó final
           if((r->info != N*N) && (r != NULL)){
                      tabuleiro[r->lin][r->col] = r->info;

                      if(x == 0){
                           x = buscar_o_no_final(r->direita, N, tabuleiro, x);
                      }
                      if(x == 0){
                           x = buscar_o_no_final(r->esquerda, N, tabuleiro, x);
                      }
                      if(x == 0){
                           x = buscar_o_no_final(r->baixo, N, tabuleiro, x);
                      }
                      if(x == 0){
                           x = buscar_o_no_final(r->cima, N, tabuleiro, x);
                      }

           }else if(r->info == N*N){
                 tabuleiro[r->lin][r->col] = r->info;//último elemento do tabuleiro. Encontramos o nó final!
                 return 1;//Opa, indicamos que o final foi encontrado e que já podemos encerrar a função!
           }
      }
      return 1;
 }