#include <iostream>

/*
 Este programa está basado en el 7.24 d . En este caso hace exactamente lo mismo nada más que la heurística cambia dinamicamente.
 Por lo tanto logramos que todos los paseos sean completos.

*/
#define FILAS 8
#define COLUMNAS 8

using namespace std;

struct tyPosicion{
 int x;
 int y;
};


void procesar(int [FILAS][COLUMNAS],int &);
void mostrar(int [FILAS][COLUMNAS],int);
bool intentarMoverse(int [FILAS][COLUMNAS],tyPosicion&,int&);
bool siguienteMovimiento(int [FILAS][COLUMNAS],tyPosicion,tyPosicion&);
void inicializarMovimientos(tyPosicion []);
void inicializarTablero(int [FILAS][COLUMNAS]);
void armarHeuristica(int [FILAS][COLUMNAS],int [FILAS][COLUMNAS]);

void main(){
 int tablero[FILAS][COLUMNAS];
 int cantidadMovimientos;

 inicializarTablero(tablero);
 procesar(tablero,cantidadMovimientos);
}

void procesar(int tablero[FILAS][COLUMNAS],int &movimientos;){
 bool pudoMoverse;
 int x,y;
 tyPosicion caballo;

 for(x = 0; x < FILAS; x++){      // Se haran 8 x 8 vueltas de caballo = 64 (Correspondientes a cada ubicacion en el tablero)
  for(y = 0;y < COLUMNAS; y++){
   movimientos = 1;      // Hasta ahora hizo cero movimientos
   caballo.x = x;       // Ubica al caballo en la posicion x
   caballo.y = y;       // Ubica al caballo en la posicion y
   tablero[caballo.x][caballo.y] = 1;  // Marca la posicion del caballo en el tablero

   do{
    // Intenta moverse una vez si pudo, modifica el tablero, el caballo y los movimientos
     // Modifica el tablero ya que el caballo se ha movido a una nueva posicion
     // Modifica el caballo ya que la posicion del caballo cambio
     // Modifica movimientos ya que se ha hecho un nuevo movimiento
    pudoMoverse = intentarMoverse(tablero,caballo,movimientos);  
   }while((pudoMoverse) && (movimientos < 64));

   mostrar(tablero,movimientos);      // Muestra el tablero resultante
   cin.get();
   system&#40;"cls"&#41;;

   inicializarTablero(tablero);   // Vuelve a inicializar el tablero para un nuevo paseo
  }
 }
}

bool intentarMoverse(int tablero[FILAS][COLUMNAS],tyPosicion &caballo;,int &contador;){
 bool encontro;
 tyPosicion pos,posMinimoParcialEmpates;
 tyPosicion empates[6];
 int cantEmpates;
 int minimoParcial;
 int heuristica[FILAS][COLUMNAS];
 tyPosicion movimientos[8];

 armarHeuristica(tablero,heuristica);
 inicializarMovimientos(movimientos);

   enc
  minimoParcial = 9;
  cantEmpates = 0;

  for(int i = 0;i < 8;i++){
   pos.x = caballo.x + movimientos[i].x;
   pos.y = caballo.y + movimientos[i].y;

   if((pos.x >= 0) && (pos.x < FILAS) && (pos.y >= 0) && (pos.y < COLUMNAS)){   // ¿Esta dentro del rango?
    if(tablero[pos.x][pos.y] ==0){              // ¿Esta desocupado?
     if(heuristica[pos.x][pos.y] <= minimoParcial){          // ¿Es el minimo parcial?        
      if(heuristica[pos.x][pos.y] < minimoParcial)
       cantEmpates = 0;

      empates[cantEmpates].x = pos.x;            // Me guardo las ocurrencias en un arreglo        
      empates[cantEmpates].y = pos.y;
      minimoParcial = heuristica[pos.x][pos.y];           // Me guardo el minimo     
       enc
      cantEmpates++;
     
     }
    }
   }
  }

  cantEmpates--;

  if(encontro){           // Encontro algun posible movimiento 
   if(cantEmpates==0){         // Encontro y no hay empates
    caballo.x = empates[0].x;      // No hay empates, no hay discución, el caballo debe moverse en esta posicion
    caballo.y = empates[0].y;
    contador++;
    tablero[caballo.x][caballo.y] = contador; // No hay empates, no hay discución, el tablero debe cambiar el estado de su celda.
   }
   else{               // Encontro y hay empates
    int minimo = 9;
    tyPosicion siguiente;
     bool enc

    for(int i = 0;i <= cantEmpates;i++){         // De esos empates, buscamos el elemento que tenga la menor heuristica en el siguiente movimiento hipotetico
      enc  // Y digo hipotetico porque en el siguiente movimiento no se evaluan los empates

     if(encontro){              // Si no encontro un movimiento, lo descartamos
      if(heuristica[siguiente.x][siguiente.y] < minimo){     // La heuristica de ese posible movimiento es la minima parcial?
       posMinimoParcialEmpates.x = empates[i].x;
       posMinimoParcialEmpates.y = empates[i].y;
       minimo = heuristica[siguiente.x][siguiente.y];
        enc
      }
     }

    }

    if(!encontroAlguno){    // En el casi improbable caso que no haya encontrado un siguiente movimiento en ninguno de los empates,
     caballo.x = empates[0].x;  // Debemos mover al caballo de todas formas...
     caballo.y = empates[0].y;
    }
    else{
     caballo.x = posMinimoParcialEmpates.x;
     caballo.y = posMinimoParcialEmpates.y;
    }

    contador++;
    tablero[caballo.x][caballo.y] = contador;       // Finalmente
   }
  }

 return encontro;

}

bool siguienteMovimiento(int tablero[FILAS][COLUMNAS],tyPosicion caballo,tyPosicion &siguiente;){
 int heuristica[FILAS][COLUMNAS];
 tyPosicion movimientos[8];
 bool encontro;
 tyPosicion pos;
 int cantEmpates;
 int minimoParcial;

 armarHeuristica(tablero,heuristica);
 inicializarMovimientos(movimientos);

  enc
 minimoParcial = 9;

 for(int i = 0;i < 8;i++){
  pos.x = caballo.x + movimientos[i].x;
  pos.y = caballo.y + movimientos[i].y;

  if((pos.x >= 0) && (pos.x < FILAS) && (pos.y >= 0) && (pos.y < COLUMNAS)){   // ¿Esta dentro del rango?
   if(tablero[pos.x][pos.y] ==0){              // ¿Esta desocupado?
    if(heuristica[pos.x][pos.y] < minimoParcial){          // ¿Es el minimo parcial?        
     siguiente.x = pos.x;
     siguiente.y = pos.y;
     minimoParcial = heuristica[pos.x][pos.y];           // Me guardo el minimo     
      enc
    }
   }
  }
 }

 return encontro;
}

void armarHeuristica(int tablero[FILAS][COLUMNAS],int heuristica[FILAS][COLUMNAS]){
 tyPosicion movimientos[8];
 tyPosicion pos;
 int heuristicaMovimientos;

 inicializarMovimientos(movimientos);

 // Recorremos la heuristica entera
 for(int x = 0; x < FILAS; x++){    
  for(int y = 0; y < COLUMNAS; y++){

   heuristicaMovimientos = 0;   // Inicializamos la cantidad de movimientos por cada posicion en la heuristica
   for(int i = 0; i < 8;i++){   // Por cada posición en la heuristica, recorremos sus posibles posiciones.

    // Obtenemos una de las 8 posiciones desde la que se puede acceder desde x e y
    pos.x = x + movimientos[i].x; 
    pos.y = y + movimientos[i].y;  

    if((pos.x >=0) && (pos.x < FILAS) && (pos.y >=0) && (pos.y < COLUMNAS)){  // ¿Esta en una posicion valida?
     if(tablero[pos.x][pos.y] == 0)           // ¿Esta vacia?  
      heuristicaMovimientos++;
    }
   }

   heuristica[x][y] = heuristicaMovimientos; // Finalmente asignamos cantidadMovimientos a la heuristica
  }
 }
}

void mostrarHeuristica(int heuristica[FILAS][COLUMNAS]){

 cout << endl << endl;
 
 for(int i = 0; i < FILAS; i++){
  for(int j = 0; j < COLUMNAS; j++){
   if(heuristica[i][j] >=10)
    cout << heuristica[i][j] << " ";
   else
    cout << heuristica[i][j] << "  ";
  }

  cout << endl;
 }

 cout << endl << endl;
}

void mostrar(int tablero[FILAS][COLUMNAS],int movimientos){
 cout << endl << endl;
 cout << "Total movimientos = " << movimientos << endl;

 cout << endl;

 for(int i = 0; i < FILAS; i++){
  for(int j = 0; j < COLUMNAS; j++){
   if(tablero[i][j] >=10)
    cout << tablero[i][j] << " ";
   else
    cout << tablero[i][j] << "  ";
  }

  cout << endl;
 }

 cout << endl << endl;
}

void inicializarTablero(int tablero[FILAS][COLUMNAS]){
 for(int i = 0;i < FILAS; i++)
  for(int j = 0; j < COLUMNAS; j++)
   tablero[i][j] = 0;
}


void inicializarMovimientos(tyPosicion movimientos[]){
 movimientos[0].x = 2;
 movimientos[0].y = -1;
 movimientos[1].x = 1;
 movimientos[1].y = -2;
 movimientos[2].x = -1;
 movimientos[2].y = -2;
 movimientos[3].x = -2;
 movimientos[3].y = -1;
 movimientos[4].x = -2;
 movimientos[4].y = 1;
 movimientos[5].x = -1;
 movimientos[5].y = 2;
 movimientos[6].x = 1;
 movimientos[6].y = 2;
 movimientos[7].x = 2;
 movimientos[7].y = 1;
}

/*

HEURISTICA:

 0 1 2 3 4 5 6 7

0 2 3 4 4 4 4 3 2

1 3 4 6 6 6 6 4 3

2 4 6 8 8 8 8 6 4

3 4 6 8 8 8 8 6 4 

4 4 6 8 8 8 8 6 4

5 4 6 8 8 8 8 6 4

6 3 4 6 6 6 6 4 3

7 2 3 4 4 4 4 3 2


*/