Problema con programa que resuelva el problema del Caballo usando heurística

[reethok]

Bueno, este es un programa que intenta resolver el problema del caballo (haciendo pasar un caballo en un tablero de ajedrez por todas las casillas sin repetir ninguna), usando heurística de accesibilidad, o sea, revisando (mediante un arreglo) qué movimiento conviene más hacer (calculando después de cada movimiento la accesibilidad de las casillas, o sea, desde cuantas posiciones se puede llegar a ellas).

Les dejo el programa, por alguna razón que aún no he encontrado, no entra en el ciclo while de la línea 34... les agradecería muchísimo su ayuda.

Código C++:

#include <iostream>
using std::cout;
using std::endl;
 
#include <iomanip>
using std::setw;
 
int heuristica(int, int, const int[][8], const int[][8]);
void modificarHeuristica(const int[][8], int[][8]);
 
int main()
{
  int movimiento;
  int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
  int vertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};
  int tablero[8][8] = {{},{}};
  int accesibilidad[8][8] = {{2, 3, 4, 4, 4, 4, 5, 2},
                 {3, 4, 6, 6, 6, 6, 4, 3},
                 {4, 6, 8, 8, 8, 8, 6, 4},
                 {4, 6, 8, 8, 8, 8, 6, 4},
                 {4, 6, 8, 8, 8, 8, 6, 4},
                 {4, 6, 8, 8, 8, 8, 6, 4},
                 {3, 4, 6, 6, 6, 6, 4, 3},
                 {2, 3, 4, 4, 4, 4, 5, 2}};
  
  int filaActual = 3;
  int columnaActual = 4;
  int pasos = 2;
  
  tablero[filaActual][columnaActual] = 1;
  
  modificarHeuristica(tablero, accesibilidad);
  
  while(heuristica(filaActual, columnaActual, tablero, accesibilidad) != -1)
  {
    movimiento = heuristica(filaActual, columnaActual, tablero, accesibilidad);
    filaActual += vertical[movimiento];
    columnaActual += horizontal[movimiento];
    tablero[filaActual][columnaActual] = pasos;
    modificarHeuristica(tablero, accesibilidad);
    pasos++;
  }
  
  for(int x = 0; x < 8; x++)
  {
    for(int y = 0; y < 8; y++)
    {
      cout << setw(3) << tablero[x][y];
    }
    cout << endl;
  }
  cout << endl;
  return 0;
}
 
void modificarHeuristica(const int tablero[][8], int nuevo[][8])
{
  for(int x = 0; x < 8; x++)
  {
    int movimientos = 0;
    
    for(int y = 0; y < 8; y++)
    {
      if((x - 1 > -1) && (x - 1 < 8) && (y + 2 > -1) && (y + 2 < 8) && (tablero[x-1][y+2] == 0))
    movimientos++;
      if((x - 2 > -1) && (x - 2 < 8) && (y + 1 > -1) && (y + 1 < 8) && (tablero[x-2][y+1] == 0))
    movimientos++;
      if((x - 2 > -1) && (x - 2 < 8) && (y - 1 > -1) && (y - 1 < 8) && (tablero[x-2][y-1] == 0))
    movimientos++;
      if((x - 1 > -1) && (x - 1 < 8) && (y - 2 > -1) && (y - 2 < 8) && (tablero[x-1][y-2] == 0))
    movimientos++;
      if((x + 1 > -1) && (x + 1 < 8) && (y - 2 > -1) && (y - 2 < 8) && (tablero[x+1][y-2] == 0))
    movimientos++;
      if((x + 2 > -1) && (x + 2 < 8) && (y - 1 > -1) && (y - 1 < 8) && (tablero[x+2][y-1] == 0))
    movimientos++;
      if((x + 2 > -1) && (x + 2 < 8) && (y + 1 > -1) && (y + 1 < 8) && (tablero[x+2][y+1] == 0))
    movimientos++;
      if((x + 1 > -1) && (x + 1 < 8) && (y + 2 > -1) && (y + 2 < 8) && (tablero[x+1][y+2] == 0))
    movimientos++;
      
      nuevo[x][y] = movimientos;
    }
  }
}
 
int heuristica(int x, int y, const int tablero[][8], const int tableroH[][8])
{
  int menor = 10;
  
    if((x - 1 > -1) && (x - 1 < 8) && (y + 2 > -1) && (y + 2 < 8) && (tablero[x-1][y+2] == 0))
      if(tableroH[x-1][y+2] < menor)
    menor = 0;
    if((x - 2 > -1) && (x - 2 < 8) && (y + 1 > -1) && (y + 1 < 8) && (tablero[x-2][y+1] == 0))
      if(tableroH[x-2][y+1] < menor)
    menor = 1;
    if((x - 2 > -1) && (x - 2 < 8) && (y - 1 > -1) && (y - 1 < 8) && (tablero[x-2][y-1] == 0))
      if(tableroH[x-2][y-1] < menor)
    menor = 2;
    if((x - 1 > -1) && (x - 1 < 8) && (y - 2 > -1) && (y - 2 < 8) && (tablero[x-1][y-2] == 0))
      if(tableroH[x-1][y-2] < menor)
    menor = 3;
    if((x + 1 > -1) && (x + 1 < 8) && (y - 2 > -1) && (y - 2 < 8) && (tablero[x+1][y-2] == 0))
      if(tableroH[x+1][y-2] < menor)
    menor = 4;
    if((x + 2 > -1) && (x + 2 < 8) && (y - 1 > -1) && (y - 1 < 8) && (tablero[x+2][y-1] == 0))
      if(tableroH[x+2][y-1] < menor)
    menor = 5;
    if((x + 2 > -1) && (x + 2 < 8) && (y + 1 > -1) && (y + 1 < 8) && (tablero[x+2][y+1] == 0))
      if(tableroH[x+2][y+1] < menor)
    menor = 6;
    if((x + 1 > -1) && (x + 1 < 8) && (y + 2 > -1) && (y + 2 < 8) && (tablero[x+1][y+2] == 0))
      if(tableroH[x+1][y+2] < menor)
    menor = 7;
    
    if(menor == 10)
      return -1;
    else
      return menor;    
}
 

Saludos;

[cotolon]

Y si lo depuras?

o colocas algo así como cout << menor; cout << x; cout << y;

y esas cosas para saber cuanto valen y vas viendo

[reethok]

Uso KDevelop y no le entiendo muy bien al depurador, sólo aparece un espacio en blanco con las mismas salidas que da el ejecutarlo, y al final "Exit succesful", pues sí, iré probando más couts, que poniendo uno en el while descubrí que nunca entraba en el ciclo.

Saludos :)

[reethok]

Problema arreglado, sólo tenía que incluir:

movimientos = 0; después de la línea 81, y yo rompiéndome la cabeza xD

Saludos.

[gonzo13]

Hola,

te recomiendo que para depurar el programa uses el editor Emacs y actives la opción gdb-many-windows, que aporta muchísima información. Yo también uso Kdevelop para programar (funciona de maravilla), pero lo compagino con Emacs para depurar mis programas.