• Martes 21 de Mayo de 2024, 13:06
« anterior próximo »
Páginas: [1]

Autor Tema:  Ayuda Salto De Caballo (recursion Infinita)  (Leído 1881 veces)

rafaeljosem

  • Nuevo Miembro
  • *
  • Mensajes: 4
    • Ver Perfil
Ayuda Salto De Caballo (recursion Infinita)
« en: Domingo 20 de Agosto de 2006, 04:16 »
0
Hola

Necesito ayuda con el siguiente codigo, el problema es que la funcion saltocaballo() se llama a si misma infinitamente, no se que hacer.

Este programa tiene como objetivo buscar la secuencia de saltos ha de dar un caballo de ajedrez, partiendo de una casilla cualquiera, para pasar por cada una de las casillas del tablero

Código: Text
  1.  
  2.  
  3. #define N 8
  4. #define n (N+1)
  5.  
  6. void saltocaballo(int i, int x, int y, int *exito);
  7. void escribetablero();
  8.  
  9. int tablero[n][n];
  10. int d[8][2] = {{2,1}, {1,2}, {-1,2}, {-2,1},{-2,-1}, {-1,-2},
  11. {1,-2}, {2,-1}}; // los 8 posibles movimientos del caballo se obtienen sumando
  12.                         //estos valores con la posicion actual (x,y)
  13.  
  14.  
  15. int main(void)
  16. {
  17.  
  18.   int x, y;
  19.   int solucion, i, j;
  20.  
  21.   do{
  22.     printf("\nCoordenadas iniciales del caballo ");
  23.     scanf ("%d %d", &x, &y);
  24.  
  25.    
  26.     } while ((x<1) || (x > N) ||
  27.        (y < 1) || (y > N));
  28.  
  29.        //valores iniciales del tablero
  30.   for (i = 1; i <=N; i++)
  31.     for (j = 1; j<=N; j++)
  32.       tablero[i][j] = 0;
  33.  
  34.   tablero[x][y] = 1;
  35.  
  36.         //llamada con coordenadas iniciales y primer salto
  37.   solucion = 0;
  38.   saltocaballo (2,x,y,&solucion);
  39.  
  40.   if (solucion)
  41.   {
  42.     puts("\n\tEl Problema tiene solucion:\n");
  43.     escribetablero();
  44.   }
  45.   else
  46.     puts("No se ha encontrado solución al problema\n");
  47.    
  48.   putchar('\n');
  49.   system("PAUSE");
  50.   return 0;
  51. }
  52.  
  53. void saltocaballo(int i, int x, int y, int *exito)
  54. {
  55.   int nx, ny;
  56.   int k;
  57.   *exito = 0;
  58.   k = 0;  //inicializa el conjunto de posible movimientos
  59.  
  60.   do {
  61.     k++;
  62.    
  63.     nx = (x + d[(k-1)][0]);
  64.     ny = (y + d[(k-1)][1]);
  65.  
  66.               //determina si nuevas coordenadas son aceptables
  67.     if ((nx >= 1) &&(nx <= N) &&
  68.       (ny >= 1) && (ny <= N) &&
  69.       (tablero[nx][ny] == 0))
  70.     {
  71.       tablero[nx][ny] = i;  //anota movimiento
  72.       if (i < (N*N))
  73.       {
  74.        
  75.         saltocaballo((i+1), nx, ny, exito);
  76.         if (!(*exito)) //no se alcanzo solucion
  77.         {
  78.          
  79.           tablero[nx][ny] = 0; //se borra anotación
  80.         }
  81.       }
  82.       else
  83.         *exito = 1; //caballo ha cunierto el tablero
  84.     }
  85.   }while ((k < 8) && !(*exito));
  86.  
  87.  
  88. }
  89.  
  90.  
  91.  
  92.  

falcatin

  • Miembro activo
  • **
  • Mensajes: 28
    • Ver Perfil
Re: Ayuda Salto De Caballo (recursion Infinita)
« Respuesta #1 en: Domingo 20 de Agosto de 2006, 13:38 »
0
Ufff pues la verdad es k no tengo muxo tiempo para mirar código, pero si te sirve de algo tuve una asignatura E.D.A. donde eso lo resolvíamos con una técnica llamada backtracking, si lo miras un pokito es fácil de aprender y muy util.

rafaeljosem

  • Nuevo Miembro
  • *
  • Mensajes: 4
    • Ver Perfil
Re: Ayuda Salto De Caballo (recursion Infinita)
« Respuesta #2 en: Domingo 20 de Agosto de 2006, 17:53 »
0
Hola, el codigo que escribi lo saque de un libro, en donde se esta tratando el tema de Backtracking, el problema es que la explicacion del libro no es muy buena (y al parecer el codigo que ellos presentan para este problema tiene errores), si podrias reconmendarme algun link en donde pueda encontrar informacion sobre backtracking, te lo agradecería.

Gracias

rafaeljosem

  • Nuevo Miembro
  • *
  • Mensajes: 4
    • Ver Perfil
Re: Ayuda Salto De Caballo (recursion Infinita)
« Respuesta #3 en: Domingo 20 de Agosto de 2006, 20:39 »
0
Ya pude resolver el problema. El codigo que habia puesto no tenia ningun error, el problema estaba en que al hacer N = 8, el programa buscaba la solucion dentro de un numero muy grande de combinaciones, por lo que demoraba demasiado tiempo. Me di cuenta al copiar otro codigo que encontre en internet, y me hacia lo mismo, asi que hice N = 5 y funciono  :D
Páginas: [1]
« anterior próximo »