Paseo del caballo en C++
May 15th, 2010 by diegomichel No comments yet
Usando Heurística, Ejercicio del libro Como Programar C++ 6ed de Deitel.
#include <iostream>
using std::cout;
using std::endl;
int siguientepaso(const int&,const int&, int[][8]);
int main(int argc, char** argv) {
int tablero[8][8]={0};
//Posicion actual del caballo
int filaActual = 0;
int columnaActual = 0;
//Movimientos posibles del caballo
int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
int vertical[8]={-1,-2,-2,-1,1,2,2,1};
int siguientemovimiento;
//Moviendo el caballo
for(int i=1;i<=64;i++)
{
//Marcando la casilla en la que estamos
tablero[filaActual][columnaActual] = i;
siguientemovimiento = siguientepaso(filaActual,columnaActual,tablero);
if(siguientemovimiento != -1)
{
filaActual += vertical[siguientemovimiento];
columnaActual += horizontal[siguientemovimiento];
}
//Ya no existe movimiento posible
if(tablero[filaActual][columnaActual] > 0)
{
cout << "Movimientos realizados: "<< i<< endl;
for(int fila=0;fila<8;fila++)
{
for(int col=0;col<8;col++)
{
cout << ""<< tablero[fila][col]<< "\t";
}
cout << "\n\n\n";
}
break;
}
}
return 0;
}
//Seleccionar el siguiente paso a hacer
int siguientepaso(const int &fila,const int &columna,int tablero[][8])
{
int accesibilidad[8][8]={
{2,3,4,4,4,4,3,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,3,2}
};
//Movimientos posibles del caballo
int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
int vertical[8]={-1,-2,-2,-1,1,2,2,1};
int bestmove = -1;
for(int movimiento=0;movimiento<8;movimiento++)
{
if((fila + vertical[movimiento]) > 7 || (fila + vertical[movimiento]) < 0)
continue;
if((columna + horizontal[movimiento]) > 7 || (columna + horizontal[movimiento]) < 0)
continue;
if(tablero[fila + vertical[movimiento]][columna + horizontal[movimiento]] > 0)
continue;
if(bestmove==-1)
{
bestmove = movimiento;
continue;
}
if(accesibilidad[fila + vertical[bestmove]][columna + horizontal[bestmove]] > accesibilidad[fila + vertical[movimiento]][columna + horizontal[movimiento]])
{
bestmove = movimiento;
}
}
return bestmove;
}