SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: vertrigo en Viernes 20 de Febrero de 2009, 17:45

Título: Salto de caballo y backtracking
Publicado por: vertrigo en Viernes 20 de Febrero de 2009, 17:45

Estoy tratando de hacer el codigo del salto del caballo ahora que estoy aprendiendo a usar backtracking pero tengo un problema con el codigo que cuando lo ejecuto me muestra el tablero de ajedrez con posiciones que no corresponden al salto que deberia dar el caballo

el codigo de la funcion que ejecuta el metodo de backtracking es el siguiente

Citar

bool moverCaballo(int x,int y,int cont) {
   
     bool listo = false;
             
        mat

• [y] = cont;

           
     if ( cont == N*N) {
          return true;    
     }  
     
     if ( !listo && verificarCasilla(x+2,y+1) ) {
          listo = moverCaballo(x+2,y+1,++cont);
     }
     
     
     if ( !listo && verificarCasilla(x+1,y+2) ) {
          listo = moverCaballo(x+1,y+2,++cont);
     }
     
     
     if ( !listo && verificarCasilla(x-1,y+2) ) {
          listo = moverCaballo(x-1,y+2,++cont);    
     }
     
     
     if ( !listo && verificarCasilla(x-2,y+1) ) {
          listo = moverCaballo(x-2,y+1,++cont);
     }
     
              // izquierda
     
     if ( !listo && verificarCasilla(x+2,y-1) ) {
          listo = moverCaballo(x+2,y-1,++cont);    
     }
     
     
     if ( !listo && verificarCasilla(x+1,y-2) ) {
          listo = moverCaballo(x+1,y-2,++cont);
     }
     
     if ( !listo && verificarCasilla(x-1,y-2) ) {
          listo = moverCaballo(x-1,y-2,++cont);
     }
     
     if ( !listo && verificarCasilla(x-2,y-1) ) {
          listo = moverCaballo(x-2,y-1,++cont);    
     }
     
          if( !listo) {
              mat

• [y] = 0;  

          }

     return listo;
     
}

El metodo que verifica que una casilla sea valida

Citar

bool verificarCasilla(int x,int y) {
     if ( mat

• [y] != 0 ) {

        return false;    
     }
     else if ( x >=N || y >= M || x < 0 || y < 0 ) {
        return false;    
     }
  return true;  
}

Y la funcion principal

Citar

#define N 5
#define M 5

int mat[N][M] = {0};

int main() {
   
    moverCaballo(0,0,1);
    imprimirMatriz();

    system("pause");
    return 0;
}

pero el resultado que muestra es el siguiente

Citar

1 11 16 0 0
18 23 0 10 15
12 2 5 20 7
25 19 8 14 4
0 13 3 6 0
Presione una tecla para continuar . . .

cuando lo que me deberia mostrar es lo siguiente
Cita:

Citar

1 16 11 6 3
10 5 2 17 12
15 22 19 4 7
20 9 24 13 18
23 14 21 8 25

Por mas que pienso y busco no consigo encontrar la falla lo mas seguro es que sea un error logico pero no logro encontrarlo les agradeceria si mi ayudaran a encontrar el error para solucionarlo

Título: Re: Salto de caballo y backtracking
Publicado por: punteroNULO en Viernes 20 de Febrero de 2009, 22:17

El problema es que al recorrer recursivamente las funciones incrementas la variable cont antes de la llamada.

Por ejemplo: (suponiendo cont = 1)

Código: C

1.  
2. //llamamos a la función (antes incrementamos, cont =2);
3. listo = moverCaballo(x+2,y+1,++cont);
4.  
5. //suponiendo que no se alcanza el resultado por ese camino se regresa hacia atrás y se intenta con la siguiente opción
6. // pero volvemos a incrementar, cont = 3, cuando debería tener el valor 2
7. listo = moverCaballo(x+1,y+2,++cont);
8.  
9.  

En cada intento estás aumentando el valor del contador cuando solo se debería sumar una vez en la función.

La solución es sencilla.
Incrementar la variable al principio de la función.

Código: C

1.  
2. bool moverCaballo(int x,int y,int cont) {
3.  
4. bool listo = false;
5. cont++;
6. mat[x][y] = cont;
7. ....
8. }
9.  
10.  

Ahora no hace falta incrementar la variable en cada llamada a función:

Código: C

1. //por ejemplo
2. listo = moverCaballo(x+2,y+1,cont);
3.  

Y como último paso modificar la llamada incial, empezando en 0.

Código: C

1. moverCaballo(0,0,0);
2.  

Título: Re: Salto de caballo y backtracking
Publicado por: vertrigo en Sábado 21 de Febrero de 2009, 05:05

Muchisimas gracias pana no me habia fijado de ese detalle ya el code funciona perfectamente de verdad te lo agradezco

 :good: