[pierrot]

Bueno lo he comprobado de las 2 formas y de la forma nueva que me has dicho tarda 7,9 minutos y con la antigua 8,1 minutos.

En mi computadora, haciendo un benchmark con el for completo, o sea con suma en el rango 0..36, obtengo en el primer caso

45m 44.651s

y en el segundo,

33m 38.615s

Bueno lo he comprobado de las 2 formas y de la forma nueva que me has dicho tarda 7,9 minutos y con la antigua 8,1 minutos.
Le he preguntado a mi profesora si tengo que imprimirlo o no, si me dice que no hace falta imprimirlo pues lo borro y ya te dire si va más rápido o no.

Es seguro que va a ser más rápido.

Lo de manejar hilos a qué te refieres porque creo que eso no lo hemos dado porque no me suena lo de manejar hilos.

Me refiero a esto. Éste es un típico caso donde el uso de hilos puede disminuir considerablemente el tiempo de retorno.


Otra cosa que puedes hacer es: cambiar la lógica del algoritmo para en un mismo backtracking obtener todas las matrices que cumplen que cada fila, cada columna y las dos diagonales suman lo mismo, independientemente de cuál sea esa cantidad. Yo lo hice así (con el for) porque en un principio había leído mal la letra y quería salvar la objeción de luis sin cambiar demasiado mi código.

[pepeluromero]

Bueno pero si no hago el for completo del 0...36 y lo hago del 0 al 18 mejor ya que me tarda mucho menos y me da la misma solución no?
Vale pues lo pongo de la nueva forma aunque solo hay unos segundos de diferencia.
Lo he estado intentando pero no se me ocurre cambiar la lógica del backtracking.

[pepeluromero]

Pablo he hecho una cosa: he puesto las funciones esValido(), actualizar() y desactualizar() de tu nueva forma pero ademas he quitado el último fragmento de esValido() y he hecho la función esSolucion() tal y como hicimos anteriormente y lo he compilado y ya me tarda un poco menos antes me tardaba 7,9 minutos más o menos y ahora me tarda unos 6,6 minutos. Sigue siendo ineficiente un poco no?
Lo malo es que no se cambiar la lógica del backtracking...

[pierrot]

Lo malo es que no se cambiar la lógica del backtracking...

Con las ideas expuestas en este hilo, tienes herramientas de sobra como para cambiarlo tú mismo. Te hice además dos preguntas para saber si estás entendiendo el funcionamiento del algoritmo pero las has ignorado. Si te preocuparas por entender qué está haciendo tu programa seguro el ejercicio sería mucho más productivo.

[pepeluromero]

La verdad es que he leído todo y lo he intentado entender pero no consigo entenderlo.
En el main creo la matriz inicializándolo a 0. Después entro en el for y dentro del for entramos en el backtracking donde n=0, luego al ir a la función esValido() no entiendo porque pones n--.

[pierrot]

En el main creo la matriz inicializándolo a 0. Después entro en el for y dentro del for entramos en el backtracking donde n=0, luego al ir a la función esValido() no entiendo porque pones n--.

Ciertamente, la primera vez para cada backtracking, cuando se hace n--, n queda con el valor -1, pero como no hay ningún valor del switch para -1, se lo saltea y esValido() devuelve verdadero.

[pepeluromero]

Y porque hay que poner n-- que en el primer caso sería n=-1??
Despues tengo otra duda:

void Backtracking(Matriz *M, int n, int *cantSol, int S, FILE *f)
{
      int k;
      if ( esValido(M, n, S)==1 )
        {
            if( esSolucion(M,n,S)==1 )
            {
                //imprimir(M, f);//
                  (*cantSol)++;
            } else if(n<16)
            {
                  for(k=0; k<10; k++)
                  {
                        M->tupla[n] = k;
                        actualizar(M, n);
                        Backtracking(M, n+1, cantSol, S, f);
                        desactualizar(M, n);
                        M->tupla[n] = 0;
                  }
            }
        }
}

Empecemos con el caso n=0: va a la función esValido() y como en el switch no hay ningún caso para n=-1 pues devuelve 1(verdadero) después entra en esSolucion() y como n!=16 pues devuelve 0(falso) como es n=0 entra en el else if(n<16), y ahora en el for pone tupla[0]=0(ya que n=0 y el for empieza en k=0), después vamos a la función actualizar y como n=0 pues en sumaDiag1(que está inicializado como 0) le sumamos tupla[0] que en este caso es 0 y tambien le suma 0 a sumasFila[0] y sumasColumna[0]. Ahora volvemos a entrar en el backtracking pero con n=1*(A partir de aquí empiezan mis dudas)*. Creo que hasta aquí lo entiendo bastante bien(si es que todo lo que he dicho llevo razón) pero ahora tengo varias dudas*:
1- al entrar otra vez en el backtracking empezamos otra vez comprobándolo en la función esValido()...y todo lo que he explicado antes no?      Pero entonces cuando entramos en la función desactualizar y M->tupla[n] = 0??
2-Cuando hace el for k=1,k=2...k=9??

[pierrot]

Revisa el documento adjunto.

[pepeluromero]

Ya lo he leído pero sigo sin entender una cosa: te voy a poner el ejemplo del backtracking de cuando n=0:

void Backtracking(Matriz *M, int n , int *cantSol, int S, FILE *f)
{
      int k;
      if ( esValido(M, n, S)==1 )
        {
            if( esSolucion(M,n,S)==1 )
            {
                //imprimir(M, f);//
                  (*cantSol)++;
            } else if(n<16)
            {
                  for(k=0; k<10; k++)
                  {
                        M->tupla[n] = k;
                        actualizar(M, n);
                        Backtracking(M, n+1, cantSol, S, f);
                        desactualizar(M, n);
                        M->tupla[0] = n;
                  }
            }
        }
}
Cuando n=0,como en la función esValido() tenemos n-- sería n=-1, luego devolvería return 1.Vemos que se cumple la función esValido() y pasamos al  if( esSolucion(M,n,S)==1 ). Como n=0, se tiene que n es distinto de 16 luego devuelve return 0 y no se cumple el if por tanto nos vamos al else if(n<16). Ahora (M->tupla[0] = 0) lo que nos hace es que le da el valor 0 a tupla[0]. Después (actualizar(M, 0) ) lo que hace es que le suma 0 a sumaDiag1, sumasFila y sumasColumna(es decir, que sigue siendo sumaDiag1=0, sumasFila=0 y sumasColumna=0). Después volvemos a empezar de nuevo el Backtracking(M, 0+1, cantSol, S, f) pero ahora con n=1 en vez de con n=0.

¿Y ahora lo que hace es que desactualiza lo que hemos hecho antes con n=0 o con n=1?¿Y nos vuelve a dar el valor 0 a tupla[0] o a tupla[1]?
Es que tengo esta duda porque como (desactualizar(M, n)) y (M->tupla[n] = 0) están después del  Backtracking(M, 0+1, cantSol,S,f) nose si la n se refiere ahora a n=1 o a n=0.

Y otra duda: ¿el for cuándo pasa a k=1,k=2...,k=9?.

Gracias por estar ayudándome Pablo.

[pierrot]

Ya lo he leído pero sigo sin entender una cosa: te voy a poner el ejemplo del backtracking de cuando n=0:

void Backtracking(Matriz *M, int n , int *cantSol, int S, FILE *f)
{
      int k;
      if ( esValido(M, n, S)==1 )
        {
            if( esSolucion(M,n,S)==1 )
            {
                //imprimir(M, f);//
                  (*cantSol)++;
            } else if(n<16)
            {
                  for(k=0; k<10; k++)
                  {
                        M->tupla[n] = k;
                        actualizar(M, n);
                        Backtracking(M, n+1, cantSol, S, f);
                        desactualizar(M, n);
                        M->tupla[0] = n;
                  }
            }
        }
}
Cuando n=0,como en la función esValido() tenemos n-- sería n=-1, luego devolvería return 1.Vemos que se cumple la función esValido() y pasamos al  if( esSolucion(M,n,S)==1 ). Como n=0, se tiene que n es distinto de 16 luego devuelve return 0 y no se cumple el if por tanto nos vamos al else if(n<16). Ahora (M->tupla[0] = 0) lo que nos hace es que le da el valor 0 a tupla[0]. Después (actualizar(M, 0) ) lo que hace es que le suma 0 a sumaDiag1, sumasFila y sumasColumna(es decir, que sigue siendo sumaDiag1=0, sumasFila=0 y sumasColumna=0). Después volvemos a empezar de nuevo el Backtracking(M, 0+1, cantSol, S, f) pero ahora con n=1 en vez de con n=0.

Correcto. Es decir, ha llenado la entrada \( (1,1) \) de la matriz con un cero y ahora llama a Backtracking() con n=1 para llenar la entrada \( (1,2) \).

¿Y ahora lo que hace es que desactualiza lo que hemos hecho antes con n=0 o con n=1?¿Y nos vuelve a dar el valor 0 a tupla[0] o a tupla[1]?
Es que tengo esta duda porque como (desactualizar(M, n)) y (M->tupla[n] = 0) están después del  Backtracking(M, 0+1, cantSol,S,f) nose si la n se refiere ahora a n=1 o a n=0.

Y otra duda: ¿el for cuándo pasa a k=1,k=2...,k=9?

Cada vez que llega a Backtracking(), "entra" de nuevo a este procedimiento recursivamente. Es lo que se llama una búsqueda en profundidad. Va a ejecutarse desactualizar(M, n) cuando se haya llenado la entrada \( (\lfloor n/4\rfloor,\text{$n$ mod $4$}) \) de la matriz M con un valor de k que hizo que la matriz no fuese válida. Y eso es porque hay que deshacer ese cambio antes de probar con el valor k+1 (en esa entrada).