miércoles, 5 de enero de 2011

Deitel_C++_4.24c(Recorrido del Caballo en C++, Enfoque Heurístico)

Esta es la segunda version que hice de este problema, el recorrido del caballo en c++. Primero hice el Recorrido del Caballo, Método de Fuerza Bruta más tardado de correr, puesto que se trata de un movimiento aleatorio. Este programa es bastante claro y creo que no tiene más problema que el de no cumplir con las casillas que pide al principio, esto debe solucionarse modificando el ciclo que lo controla. Sin embargo, y como mencioné en la primera entrada (Proposito, Junio de 2010) es probable que haya mas errores. Hice varias versiones del recorrido del caballo, algunas malas, respalde e instale varias veces mi sistema operativo en la maquina que usaba, ademas de que hice estos programas hace ya tiempo, por lo tanto debe revisarse este código con cuidado. Sin embargo, creo que hay una buena base para jugar con este problema clasico de los algoritmos.


#include <iostream>
 using namespace::std;
 #include <cstdlib>
 #include <ctime>

 const int Tamano_Arreglo = 8;
 int Valores( int );
 void Mueve(int A[Tamano_Arreglo][ Tamano_Arreglo ], int);

 int x = 0;
 int y = 0;
 int contador = 1;

 int main()

 { //ABRE MAIN

 srand(time(NULL));
 int Tabla[Tamano_Arreglo ][Tamano_Arreglo ] = {{0}, {0}};
 int i;
 int centinela = 1;
 int casillas_a_llenar;
 int Puedo_Mover_Aqui[Tamano_Arreglo ] = {0};
 int Valores_Accesibilidad[Tamano_Arreglo ] = {0, 0};
 cout <<"\nCuantas casillas quiere que recorra el caballo por lo menos?" <<endl;
 cin >> casillas_a_llenar;

 //ESTOS CICLOS FOR LIMPIAN EL TABLERO CADA VEZ
 // Y BORRAN LOS DATOS DE Puedo_Mover_Aqui

 for ( int j = 0; j < Tamano_Arreglo; j++ )
 {

 for( int k = 0; k < Tamano_Arreglo; k++ )
 {
 Tabla[j][k] = 0;
 }

 Puedo_Mover_Aqui[ j ] = 0;
 Valores_Accesibilidad[j] = 10;
 }

 Tabla[ y ][ x ] = 1;
 while ( casillas_a_llenar > contador && 1 == centinela )
 { //ABRE WHILE QUE CONTROLA
  //EL NUMERO DE CASILLAS QUE SE LLENARAN
 centinela = 0;
 for( int k = 0; k < Tamano_Arreglo; k++ )
 {
 Puedo_Mover_Aqui[ k ] = 0;
 Valores_Accesibilidad[k] = 10;
 }

 for ( i = 0; i < Tamano_Arreglo; i++ )

 { //ABRE FOR
 switch (i)
 { //ABRE SWITCH

 case 0:
 {
 if ( x + 2 < Tamano_Arreglo && y - 1 >= 0 )
 {
 if ( Tabla[y - 1][x + 2] == 0 )
 {
 Puedo_Mover_Aqui[i] = 1;
 }

 }
 break;
 }

 case 1:
 {

 if ( x + 1 < Tamano_Arreglo && y - 2 >= 0 )
 {
 if ( Tabla[y - 2][x + 1] == 0 )
 {
 Puedo_Mover_Aqui[i] = 1;
 }
 }
 break;

 }

 case 2:
 {

 if ( x - 1 >= 0 && y - 2 >= 0 )
 {
 if ( Tabla[y - 2][x - 1] == 0 )
 {
 Puedo_Mover_Aqui[i] = 1;
 }
 }
 break;
 }
 case 3:
 {
 if ( x - 2 >= 0 && y - 1 >= 0 )
 {
 if ( Tabla[y - 1][x - 2] == 0 )
 {
 Puedo_Mover_Aqui[i] = 1;
 }
 }
 break;
 }

 case 4:
 {
 if ( x - 2 >= 0 && y + 1 < Tamano_Arreglo )
 {
 if ( Tabla[y + 1][x - 2] == 0 )
 {
 Puedo_Mover_Aqui[i] = 1;
 }
 }
 break;
 }
 case 5:

 {

 if ( x - 1 >= 0 && y + 2 < Tamano_Arreglo )
 {
 if ( Tabla[y + 2][x - 1] == 0 )
 {
 Puedo_Mover_Aqui[i] = 1;
 }
 }
 break;
 }
 case 6:

 {
 if ( x + 1 < Tamano_Arreglo && y + 2 < Tamano_Arreglo )
 {
 if ( Tabla[y + 2][x + 1] == 0 )
 {
 Puedo_Mover_Aqui[i] = 1;
 }
 }
 break;

 }

 case 7:
 {
 if ( x + 2 < Tamano_Arreglo && y + 1 < Tamano_Arreglo )
 { //ABRE IF
 if ( Tabla[y + 1][x + 2] == 0 )
 { //ABRE IF ANIDADO
 Puedo_Mover_Aqui[i] = 1;
 } //CIERRA IF ANIDADO
 } // CIERRA IF 
 break;
 }
 default:
 {
 cout << "EL CONTADOR i NO ESTA DANDO LOS NUMEROS CORRECTOS" << endl;
 cout << "el contador es: " << i << endl;
 break;

 }
 } //CIERRA SWITCH
 } //CIERRA FOR
 
 for ( i = 0; i < Tamano_Arreglo; i++ )
 {
 if ( 1 == Puedo_Mover_Aqui[i] )
 {
 centinela = 1;
 }
 }
 if ( 1 == centinela )
 { // ABRE IF
 for ( i = 0; i < Tamano_Arreglo; i++ )
 { //ABRE FOR
 if ( 1 == Puedo_Mover_Aqui[ i ])
 { //ABRE IF ANIDADO
 Valores_Accesibilidad[i] = Valores(i);
 } //CIERRA IF
 } //CIERRA FOR

 int menor = Valores_Accesibilidad[0];
 int movimiento_a_hacer = 0;

 for ( i = 1; i < Tamano_Arreglo; i++ )
 {
 if ( Valores_Accesibilidad[i] < menor )
 {
 menor = Valores_Accesibilidad[i];
 movimiento_a_hacer = i;
 }

 if ( Valores_Accesibilidad[i] == menor )
 {
 int aguila_o_sol = rand() % 2;
 if ( 0 == aguila_o_sol )
 movimiento_a_hacer = i;
 }
 }

 ++contador;
 Mueve( Tabla, movimiento_a_hacer);

 } // CIERRA IF
 } //CIERRA WHILE

 cout <<"El contador es: " << contador << endl;
 for ( int d = 0; d < Tamano_Arreglo; d++ )
 {
 for( int k = 0; k < Tamano_Arreglo; k++ )
 {
 if ( 0 == Tabla[d][k] && 0 == Tabla[d][k] / 10 )
   //MODIFICADA LA LINEA DE ARRIBA
 cout << " ";
 cout << Tabla[d][k] << " ";
 }
 cout << endl <<endl;
 }

 return 0;

 } //CIERRA MAIN


 ////////////////////////////////////////////////////////////////////
 // FUNCION VALORES
 ////////////////////////////////////////////////////////////////////

 int Valores(int movimiento)

 { // ABRE VALORES
 int Accesibilidad[Tamano_Arreglo + 1][Tamano_Arreglo + 1] =

 {

 { 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 }

 };

 switch (movimiento)

 { //ABRE SWITCH

 case 0:
 {
 return Accesibilidad[y - 1][x + 2];
 break;
 }

 case 1:
 {
 return Accesibilidad[y - 2][x + 1];
 break;
 }
 case 2:
 {
 return Accesibilidad[y - 2][x - 1];
 break;
 }
 case 3:
 {
 return Accesibilidad[y - 1][x - 2];
 break;
 }

 case 4:
 {
 return Accesibilidad[y + 1][x - 2];
 break;
 }

 case 5:
 {
 return Accesibilidad[y + 2][x - 1];
 break;
 }

 case 6:
 {
 return Accesibilidad[y + 2][x + 1];
 break;
 }

 case 7:
 {
 return Accesibilidad[y + 1][x + 2];
 break;
 }

 default:

 {
 cout << "EL MOVIMIENTO ES ILEGAL" << endl;
 cout << "EL MOVIMIENTO ES: " << movimiento << endl;
 return -1;
 break;
 }
 } //CIERRA SWITCH

 } //CIERRA FUNCION VALORES


 /////////////////////////////////////////////////////////////
 //FUNCION MUEVE
 /////////////////////////////////////////////////////////////

 void Mueve(int A[Tamano_Arreglo][Tamano_Arreglo ], int movimientos )

 { // ABRE VALORES
 switch (movimientos)

 { //ABRE SWITCH
 case 0:
 {
 y -= 1;
 x += 2;
 A[y ][x ] = contador;
 break;
 }

 case 1:
 {
 y -= 2;
 x += 1;
 A[y ][x ] = contador;
 break;
 }

 case 2:
 {
 y -= 2;
 x -= 1;
 A[y ][x ] = contador;
 break;

 }

 case 3:
 {
 y -= 1;
 x -= 2;
 A[y ][x ] = contador;
 break;
 }

 case 4:
 {
 y += 1;
 x -= 2;
 A[y ][x ] = contador;
 break;
 }

 case 5:
 {
 y += 2;
 x -= 1;
 A[y][x ] = contador;
 break;
 }

 case 6:
 {
 y += 2;
 x += 1;
 A[y ][x ] = contador;
 break;
 }

 case 7:
 {
 y += 1;
 x += 2;
 A[y ][x ] = contador;
 break;
 }

 default:

 {
 cout << "EL MOVIMIENTO ES ILEGAL" << endl;
 cout << "EL MOVIMIENTO ES: " << movimientos << endl;
 break;
 }

} //CIERRA SWITCH

 return;

 } //CIERRA FUNCION MUEVE

4 comentarios:

  1. he estado estudiando este problema y buscando literatura al respecto.....y he conseguido codificar un par de algoritmos de retroceso y de heuristica voraz creo que un poco mas simple...q esta version ..que consegui aqui...


    ------------------

    ResponderEliminar
  2. #include
    #define N 8
    enum bool {FALSE,TRUE};
    typedef enum bool boolean;
    //#define ncuad N*N
    int ejex[8]={2,1,-1,-2,-2,-1,1,2};
    int ejey[8]={1,2,2,1,-1,-2,-2,-1};
    int tablero[N][N];

    int acesible( int x,int y);
    void mover(int tablero[][N], int x,int y,int *q);





    int main(void)
    {
    int x;int y;

    int i,j;
    int menor;
    //int m1,m2;
    int peso[8]={0,1,2,3,4,5,6,7};
    int k,u,v;
    int num;
    int kk;

    boolean parar;

    // int tablero[N][N];

    for(i=0;i=0 && u=0 && v=0;k--)
    {
    u=x+ejex[k];v=y+ejey[k];
    if(u>=0 && u=0 && v<N)
    {
    if(tablero[u][v]==0)
    num=num+1;
    //printf("%d",num);

    }



    }
    return num;
    }

    ResponderEliminar
  3. ---AQUEL FUE HEURISTICA Y ESTE RETROCESO(BACK)---

    #include
    #define N 8
    #define ncuad N*N

    void mover(int tablero[][N],int i,int pos_x,int pos_y,int *q);

    int ejex[8]={2,1,-1,-2,-2,-1,1,2};
    int ejey[8]={1,2,2,1,-1,-2,-2,-1};

    int main(void)
    {

    int tablero[N][N];/*tablero de ajedrez*/

    int i,j,q;

    /*inicializa el tablero a cero*/

    for(i=0;i=0 && u=0 && v<N){ /*esta dentro de los limites*/
    if(tablero[u][v]==0){/*¿es valido?*/
    tablero[u][v]=i;
    if(i<ncuad) { /*llega al final del recorrido*/
    mover(tablero,i+1,u,v,q);
    if(!*q) tablero[u][v]=0;
    }
    else
    *q=1;/*hay solucion*/
    }

    }
    k++;

    }while(!*q && k<8);
    }

    ResponderEliminar
  4. Hola, Muchas gracias por tus programas. La verdad es que sí es un programa bastante largo el que escribí. Voy a revisar los que pusiste. Gracias.

    ResponderEliminar

Related Posts Plugin for WordPress, Blogger...