Autor Tema: Criss Cross en C

0 Usuarios y 1 Visitante están viendo este tema.

01 Junio, 2015, 02:34 pm
Respuesta #20

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Pero si borro el código de esValido() despues en el Backtracking no puedo poner esValido no? Deberíamos de borrar del backtracking esValido()

Yo no digo borrar esValido() sino copiar el fragmento que citaste para esSolucion().
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

01 Junio, 2015, 02:52 pm
Respuesta #21

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Vale ya te he entendido, ¿entonces pongo esto no?

int esValido(Matriz *M, int n, int S)
{
      int i;
      /* Chequeo filas */
      for(i=0; i<4; i++)
        {
            if (M->sumasFila[i] > S)
            {
                  return 0;
            }
        }
      if( n>=4 && M->sumasFila[0] != S)
        {
          return 0;
        }
      else if ( n>=8 && M->sumasFila[1] != S)
        {
            return 0;
        }
      else if ( n>=12 && M->sumasFila[2] != S)
        {
            return 0;
        }

      /* Chequeo columnas */
      for(i=0; i<4; i++)
        {
            if (M->sumasColumna[i] > S)
            {
                  return 0;
            }
        }
      if( n>=13 && M->sumasColumna[0] != S)
      {
          return 0;
      }
      else if ( n>=14 && M->sumasColumna[1] != S)
        {
            return 0;
        }
      else if ( n>=15 && M->sumasColumna[2] != S)
      {
          return 0;
      }

      /* Chequeo diagonales */
      if (M->sumaDiag1 > S || M->sumaDiag2 > S)
        {
            return 0;
        }
      if ( n>=13 && M->sumaDiag2 != S)
        {
            return 0;
        }
       if ( n>=16 && M->sumaDiag1 != S)
        {
            return 0;
        }

      return 1;
}

int esSolucion(Matriz *M, int n, int S) {
      int res;
      if( n == 16 && M->sumasFila[3]==S && M->sumasColumna[3]==S && M->sumaDiag1==S ) {
            res = 1;
      } else {
            res = 0;
      }
      return res;
}

Y en el backtracking pongo esto:

void Backtracking(Matriz *M, int n, int *cantSol, int S, FILE *f)
{
      int k;
      if ( esValido(M, n, S) )
        {
            if( esSolucion(M,n,S) )
            {
                  imprimir(M, f);
                  (*cantSol)++;
            } else
            {
                  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;
                        //}
                  }
            }
      }
}

01 Junio, 2015, 02:56 pm
Respuesta #22

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Vale ya te he entendido entonces pongo esto no?:

Sí.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

01 Junio, 2015, 03:00 pm
Respuesta #23

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Pues he puesto eso pero sólo me da la solución cuando la suma es 0, 1 y 2 a partir de 3 me da 0... luego tiene que haber algún error.

01 Junio, 2015, 04:02 pm
Respuesta #24

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Pues he puesto eso pero sólo me da la solución cuando la suma es 0, 1 y 2 a partir de 3 me da 0... luego tiene que haber algún error.

Ahora estoy en Windows, y por desgracia Windows no viene con un compilador de C, así que no puedo debuggear para ver si funciona o no correctamente. No obstante, creo que sé cuál es el problema. Prueba si añadiendo lo que está en rojo funciona:

Y en el backtracking pongo esto:

void Backtracking(Matriz *M, int n, int *cantSol, int S, FILE *f)
{
      int k;
      if ( esValido(M, n, S) )
        {
            if( esSolucion(M,n,S) )
            {
                  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;
                        //}
                  }
            }
      }
}

Si es que ahora se solucionó, ¿cuál era el problema?  ;)
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

01 Junio, 2015, 08:06 pm
Respuesta #25

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Ya me funciona ese era el error menos mal que lo has encontrado :aplauso: ;)
Ahora tengo otra preguntita todo funciona correctamente pero el codigo sigue siendo un poco ineficiente no?
Lo digo porque me tarda unos 7 minutos y pico para llegar a la solución final.
Gracias por todo.

02 Junio, 2015, 08:35 pm
Respuesta #26

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Ahora tengo otra preguntita todo funciona correctamente pero el codigo sigue siendo un poco ineficiente no?
Lo digo porque me tarda unos 7 minutos y pico para llegar a la solución final.

Como había dicho antes, el método esValido() hacía una cantidad de comparaciones innecesarias. Ahora hice una implementación más inteligente, que sólo hace las comparaciones que son estrictamente necesarias:

Cuadrado.c
#include <stdio.h>
#include <stdlib.h>
#include "Cuadrado.h"

struct _RegCuadrado {
      int tupla[16];
      int sumasFila[4];
      int sumasColumna[4];
      int sumaDiag1, sumaDiag2;
};

Cuadrado *crearCuadrado(){
      Cuadrado *C = malloc(sizeof(Cuadrado));
      int k;
      for(k=0; k<16; k++) {
            C->tupla[k] = 0;
      }
      for(k=0; k<4; k++) {
            C->sumasFila[k] = 0;
            C->sumasColumna[k] = 0;
      }
      C->sumaDiag1 = 0;
      C->sumaDiag2 = 0;
      return C;
}

void destruirCuadrado(Cuadrado *C) {
      free(C);
}

int esValido(Cuadrado *C, int n, int S) {
      n--;
      int fila = n/4;
      int columna = n%4;
      switch ( n ) {
      case 0:
      case 5:
      case 10:
            if ( C->sumasFila[fila]>S || C->sumasColumna[columna]>S || C->sumaDiag1>S  ) { return 0; }
            break;
      case 1:
      case 2:
      case 4:
      case 8:
            if ( C->sumasFila[fila]>S || C->sumasColumna[columna]>S ) { return 0; }
            break;
      case 6:
      case 9:
            if ( C->sumasFila[fila]>S || C->sumasColumna[columna]>S || C->sumaDiag2>S ) { return 0; }
            break;
      case 3:
            if ( C->sumasFila[fila]!=S || C->sumasColumna[columna]>S || C->sumaDiag2>S ) { return 0; }
            break;
      case 7:
      case 11:
            if ( C->sumasFila[fila]!=S || C->sumasColumna[columna]>S ) { return 0; }
            break;
      case 12:
            if ( C->sumasFila[fila]>S || C->sumasColumna[columna]!=S || C->sumaDiag2!=S ) { return 0; }
            break;
      case 13:
      case 14:
            if ( C->sumasFila[fila]>S || C->sumasColumna[columna]!=S ) { return 0; }
            break;
      case 15:
            if ( C->sumasFila[fila]!=S || C->sumasColumna[columna]!=S || C->sumaDiag1!=S ) { return 0; }
      }
      return 1;
}

void actualizar(Cuadrado *C, int n) {
      if( n%5 == 0 ) {
            C->sumaDiag1 += C->tupla[n];
      } else if ( n%3 == 0 ) {
            C->sumaDiag2 += C->tupla[n];
      }
      C->sumasFila[n/4] += C->tupla[n];
      C->sumasColumna[n%4] += C->tupla[n];
}

void desactualizar(Cuadrado *C, int n) {
      if( n%5 == 0 ) {
            C->sumaDiag1 -= C->tupla[n];
      } else if ( n%3 == 0 ) {
            C->sumaDiag2 -= C->tupla[n];
      }
      C->sumasFila[n/4] -= C->tupla[n];
      C->sumasColumna[n%4] -= C->tupla[n];
}

void imprimir(Cuadrado *C, FILE *f) {
      int i, j;
      for(i=0; i<4; i++) {
            for(j=4*i; j<4*i+3; j++) {
                  fprintf(f, "%d ", C->tupla[j]);
            }
            fprintf(f, "%d\n", C->tupla[j]);
      }
      fprintf(f, "-------\n");
}

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

[cerrar]

Fíjate si ahora es un poco más rápido. Si no lo es, otra posibilidad es manejar hilos para paralelizar tareas. También ten presente que si lo único que te importa es determinar cuántas soluciones hay, estás perdiendo el tiempo al imprimirlas. En caso de que sí te exijan imprimir las matrices solución, puedes procesar los casos de n=0 a n=17, imprimir las matrices y al mismo tiempo almacenar las "complementarias" en una estructura de pila, para imprimirlas después del caso n=18 y así evitar hacer el backtracking dos veces.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

02 Junio, 2015, 10:08 pm
Respuesta #27

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Yaya eso es lo que hice, en el programa he explicado que del 0 al 17 es lo mismo que del 19 al 36 entonces soloe he hecho la suma del 0 al 17 y el resultado de cada una lo multiplico por 2 y despues he hecho el backtracking cuando suma=18 y se lo he sumado al resultado que ya tenia.

for(suma=0; suma<18; suma++)
     {
            int cantSol = 0;
            Backtracking(M, 0, &cantSol, suma, fp);
            fprintf(fp, "La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es %d, es: %d\n",suma,cantSol);
            printf("La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es %d, es: %d\n",suma,cantSol);
            total1 = total1+ cantSol*2;
      }
            int cantSol = 0;
            Backtracking(M, 0, &cantSol, 18, fp);
            fprintf(fp, "La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es %d, es: %d\n",18,cantSol);
            printf("La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es %d, es: %d\n",18,cantSol);
            total2 = total2+ cantSol;

            total=total1+total2;

He probado lo que me dijistes y tarda lo mismo que antes...

02 Junio, 2015, 10:39 pm
Respuesta #28

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
He probado lo que me dijistes y tarda lo mismo que antes...

Humm... Debiera ser un poco más rápido. Prueba también eliminar la línea de imprimir() en Backtracking(). Lo otro que se me ocurre, manteniendo este algoritmo, y aprovechándonos de que el cálculo para una suma dada es independiente de otra, es manejar hilos.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

02 Junio, 2015, 10:43 pm
Respuesta #29

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
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. Lo de manejar hilos a qué te refieres porque creo que eso no lo hemos dado porque no me suena lo de manejar hilos.

03 Junio, 2015, 03:32 am
Respuesta #30

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
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.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

03 Junio, 2015, 10:07 am
Respuesta #31

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
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.

03 Junio, 2015, 10:32 am
Respuesta #32

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
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...

03 Junio, 2015, 07:03 pm
Respuesta #33

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
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.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

04 Junio, 2015, 06:23 pm
Respuesta #34

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
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--.

05 Junio, 2015, 01:51 am
Respuesta #35

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
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.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

05 Junio, 2015, 10:40 am
Respuesta #36

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
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??

06 Junio, 2015, 06:05 am
Respuesta #37

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Revisa el documento adjunto.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

06 Junio, 2015, 01:22 pm
Respuesta #38

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
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.

06 Junio, 2015, 07:27 pm
Respuesta #39

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
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).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print