Necesito ayuda ¡¡ Desplazamineto del caballo

[Marco_ant]

Hola a todos tengo una duda con este codigo( lenguaje c ), es de el movimiento del caballo de ajedrez, se supone que tiene que tiene que abarcar todos lo cuadros del tablero sin pasar por uno mas de una vez, solo que me repite números en el tablero, ayuda por favor

Código (c) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>
#define ncuad n*n
#define n 8


void mover(int matriz1[][n],int i, int pos_x, int pos_y, int *q);

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

int main (void)

{



   int matriz1[n][n],i,j,q;

   for(i=0;i<n;i++)
   {
       for(j=0;j<n;j++)
       {
           matriz1[i][j]=0;
       }
   }


   matriz1[0][0]=1;
   mover(matriz1,2,0,0,&q);

   printf("\n\t");
   printf("Estos son los valores de la matriz \n\n");
   printf("\t\t MATRIZ ORDENADA ");
   for(i=0;i<n;i++)
   {
       printf("\n");
       for(j=0;j<n;j++)
       {
           printf("%6d", matriz1[i][j]);
       }
   }

   printf("\n");


   return 0;
}
void mover(int matriz1[][n],int i, int pos_x, int pos_y, int *q)
{
 int k, u, v;

 k = 0;
 *q = 0;
 do {
   u = pos_x + ejex[k]; v = pos_y + ejey[k]; /* seleccionar candidato */
   if (u >= 0 && u < n && v >= 0 && v < n) { /* esta dentro de los limites? */
     if (matriz1[u][v] == 0) {  /* es valido? */
       matriz1[u][v] = i;  /* anota el candidato */
       if (i < ncuad) {  /* llega al final del recorrido? */
         mover(matriz1,i+1,u,v,q);
       if (*q) matriz1[u][v] = 0; /* borra el candidato */
       }
       else *q = 1; /* hay solucion */
     }
   }
   k++;
 } while (!*q && k < 8);
}



[MOD] Para publicar codigo, usar etiquetas GeShi, gracias.

[Randomize]

¡¡¡ Qué manía con poner los deberes por el foro !!! 


Yo también tengo deberes y no los pongo 

[eferion]

deberías repensar un poco el algoritmo.

Las constantes deberían ir en mayúsculas, ayuda a identificarlas dentro del código... sobretodo si le das nombres tan "currados" como "n".

Por otro lado, el parámetro "int *q" no es necesario para tu código. Puedes conseguir el mismo efecto haciendo que la función "mover" devuelva un entero para indicar si se ha encontrado una solución o no.

Luego, fíjate que tienes la línea

Código (cpp) [Seleccionar] Expandir

if (*q) matriz1[u][v] = 0; /* borra el candidato */

Es decir, si hay solución, entonces te cargas la solución encontrada?? ¿No debería ser al reves?

Aplicando los cambios a mí me funciona:

Código [Seleccionar] Expandir



        Estos son los valores de la matriz

                 MATRIZ ORDENADA
     1     8    11    16     3    18    13    64
    10    27     2     7    12    15     4    19
    53    24     9    28    17     6    63    14
    26    39    52    23    62    29    20     5
    43    54    25    38    51    22    33    30
    40    57    42    61    32    35    48    21
    55    44    59    50    37    46    31    34
    58    41    56    45    60    49    36    47

[Marco_ant]

Que cambios mencionas no te entiedo??

[leosansan]

Código (cpp) [Seleccionar] Expandir

if (!*q) matriz1[u][v] = 0; /* borra el candidato */

¡¡¡¡ Saluditos! ..... !!!!

P.D: Tarda algo más de 30 segundos en encontrar la solución.

       Estos son los valores de la matriz


                MATRIZ ORDENADA

     1     8    11    16      3    18    13   64
   10    27     2     7     12    15      4   19
   53    24      9   28    17      6    63   14
   26    39    52    23    62    29    20    5
   43    54    25    38    51    22    33   30
   40    57    42    61    32    35    48   21
   55    44    59    50    37    46    31   34
   58    41    56    45    60    49    36   47

Process returned 0 (0x0)   execution time : 32.015 s
Press any key to continue.