Autor Tema: Criss Cross en C

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

08 Mayo, 2015, 01:48 pm
Leído 6914 veces

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Una cuadrícula de tamaño 4x4 se llena de d dígitos, 0 ≤ d ≤ 9. Se puede observar que en la cuadrícula:
 6 3 3 0
 5 0 4 3
 0 7 1 4
 1 2 4 5
la suma de cada fila y cada columna tiene el valor 12. Por otra parte, la suma de cada diagonal es también 12.¿De cuántas maneras se puede rellenar una cuadrícula de 4x4 con los dígitos d, 0 ≤ d ≤ 9 de modo que cada fila, cada columna y las dos diagonales tienen la misma suma?

Por favor decirme cómo puedo hacer este ejercicio en C ya que no se me ocurre nada. Gracias por adelantado.

09 Mayo, 2015, 12:19 am
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Buenas noches,

Hay dos maneras de resolver este problema:

  • Ocurriéndosete una idea brillante de ésas que simplifican enormemente todo, y a  partir de las cuales, se hacen algoritmos sencillos y elegantes, ó

  • Aplicando fuerza bruta (pero siendo razonable, o sea, sin analizar las \( 10^{16} \) matrices posibles para ver si cumplen las condiciones).

Si estás buscando lo primero, espera por el_manco  :laugh:

Si estás buscando lo segundo, un posible algoritmo (aplicando una técnica conocida como backtracking), es éste:

#include<stdio.h>

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

void init(Cuadrado *C){
      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;
}

int esValido(Cuadrado *C, int n) {

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

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

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

      if( n == 16 ) {
            if ( C->sumasFila[3]==12 && C->sumasColumna[3]==12 && C->sumaDiag1==12 ) {
                  return 1;
            } else {
                  return 0;
            }
      }
      return 1;
}

void actualizar(Cuadrado *C, int n) {
      if( n==0 || n==5 || n==10 || n==15 ) {
            C->sumaDiag1 += C->tupla[n];
      } else if ( n==3 || n==6 || n==9 || n==12 ) {
            C->sumaDiag2 += C->tupla[n];
      }
      if(0 <= n && n <= 3) { C->sumasFila[0] += C->tupla[n]; }
      else if(4 <= n && n <= 7) { C->sumasFila[1] += C->tupla[n]; }
      else if(8 <= n && n <= 11) { C->sumasFila[2] += C->tupla[n]; }
      else if(12 <= n && n <= 15) { C->sumasFila[3] += C->tupla[n]; }
      C->sumasColumna[n%4] += C->tupla[n];
}

void desactualizar(Cuadrado *C, int n) {
      if( n==0 || n==5 || n==10 || n==15 ) {
            C->sumaDiag1 -= C->tupla[n];
      } else if ( n==3 || n==6 || n==9 || n==12 ) {
            C->sumaDiag2 -= C->tupla[n];
      }
      if(0 <= n && n <= 3) { C->sumasFila[0] -= C->tupla[n]; }
      else if(4 <= n && n <= 7) { C->sumasFila[1] -= C->tupla[n]; }
      else if(8 <= n && n <= 11) { C->sumasFila[2] -= C->tupla[n]; }
      else if(12 <= n && n <= 15) { C->sumasFila[3] -= C->tupla[n]; }
      C->sumasColumna[n%4] -= C->tupla[n];
}

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

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

int main(void) {
      Cuadrado C;
      init( &C );
      int cantSol = 0;
      Backtracking(&C, 0, &cantSol);
      printf("La cantidad total de cuadrados cumpliendo los requisitos es: %d",cantSol);
      return 0;
}


Imprime todos los cuadrados posibles, y la cantidad exacta al final. Son 209127  :o. Si tienes alguna duda sobre este programa, no dudes en preguntar.

Saludos.

PD. Yo hace mucho no programo en C (de hecho, este programa lo escribí en Perl y luego hice la traducción a C, pero me resultó engorroso dada la cantidad de errores de sintaxis que cometí). Seguro que algún purista de C pondría el grito en el cielo (de la misma manera que hago yo cuando veo código Perl de otras personas  >:D). Si eres uno de esos puristas de C (como creo que es argentinator  :laugh:),  haz tú las correcciones que consideres pertinentes. Lo importante es el algoritmo empleado más allá del lenguaje de programación.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

09 Mayo, 2015, 03:16 am
Respuesta #2

luis

  • Aprendiz
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino
¿De cuántas maneras se puede rellenar una cuadrícula de 4x4 con los dígitos d, 0 ≤ d ≤ 9 de modo que cada fila, cada columna y las dos diagonales tienen la misma suma?

el programa que manda pablon aspira a encontrar los cuadrados en que la suma sea doce. creo que el problema es encontrar los cuadrados en que la suma sea la misma, doce, o trece, o cero (el caso inicial en el programa de pabloN).

saludos

luis

09 Mayo, 2015, 03:53 am
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
el programa que manda pablon aspira a encontrar los cuadrados en que la suma sea doce. creo que el problema es encontrar los cuadrados en que la suma sea la misma, doce, o trece, o cero (el caso inicial en el programa de pabloN).

Cierto. Leí mal el enunciado del problema (de la misma manera en que leí mal una vez el enunciado de un problema en un examen de lógica   :'(). Pero lo arreglamos fácil (las modificaciones están en rojo):

#include<stdio.h>

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

void init(Cuadrado *C){
      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;
}

int esValido(Cuadrado *C, int n, int S) {

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

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

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

      if( n == 16 ) {
            if ( C->sumasFila[3]==S && C->sumasColumna[3]==S && C->sumaDiag1==S ) {
                  return 1;
            } else {
                  return 0;
            }
      }
      return 1;
}

void actualizar(Cuadrado *C, int n) {
      if( n==0 || n==5 || n==10 || n==15 ) {
            C->sumaDiag1 += C->tupla[n];
      } else if ( n==3 || n==6 || n==9 || n==12 ) {
            C->sumaDiag2 += C->tupla[n];
      }
      if(0 <= n && n <= 3) { C->sumasFila[0] += C->tupla[n]; }
      else if(4 <= n && n <= 7) { C->sumasFila[1] += C->tupla[n]; }
      else if(8 <= n && n <= 11) { C->sumasFila[2] += C->tupla[n]; }
      else if(12 <= n && n <= 15) { C->sumasFila[3] += C->tupla[n]; }
      C->sumasColumna[n%4] += C->tupla[n];
}

void desactualizar(Cuadrado *C, int n) {
      if( n==0 || n==5 || n==10 || n==15 ) {
            C->sumaDiag1 -= C->tupla[n];
      } else if ( n==3 || n==6 || n==9 || n==12 ) {
            C->sumaDiag2 -= C->tupla[n];
      }
      if(0 <= n && n <= 3) { C->sumasFila[0] -= C->tupla[n]; }
      else if(4 <= n && n <= 7) { C->sumasFila[1] -= C->tupla[n]; }
      else if(8 <= n && n <= 11) { C->sumasFila[2] -= C->tupla[n]; }
      else if(12 <= n && n <= 15) { C->sumasFila[3] -= C->tupla[n]; }
      C->sumasColumna[n%4] -= C->tupla[n];
}

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

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

int main(void) {
      Cuadrado C;
      init( &C );
      int cantSol = 0;
      int total = 0, suma = 0;
      for(suma=0; suma<=36; suma++) {
            Backtracking(&C, 0, &cantSol, suma);
            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);
            total += cantSol;

      }
      printf("Total: %d", total);
      return 0;
}
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

09 Mayo, 2015, 04:03 am
Respuesta #4

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Cambiando suma <= 36 por suma <= 1, la salida sería:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
-------
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 0, es: 1
0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
-------
0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0
-------
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
-------
0 0 1 0
1 0 0 0
0 1 0 0
0 0 0 1
-------
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
-------
0 1 0 0
0 0 1 0
1 0 0 0
0 0 0 1
-------
1 0 0 0
0 0 0 1
0 1 0 0
0 0 1 0
-------
1 0 0 0
0 0 1 0
0 0 0 1
0 1 0 0
-------
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 1, es: 9
Total: 10

En el for puse suma <= 36 para considerar todos los casos posibles (hasta la cuadrícula que tiene 9 en todas sus entradas).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

09 Mayo, 2015, 06:47 am
Respuesta #5

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Aquí hay un pequeño error:

int main(void) {
      Cuadrado C;
      init( &C );
      int cantSol = 0;
      int total = 0, suma = 0;
      for(suma=0; suma<=36; suma++) {
            Backtracking(&C, 0, &cantSol, suma);
            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);
            total += cantSol;

      }
      printf("Total: %d", total);
      return 0;
}


La línea en negrita debe ir en este lugar:

int main(void) {
      Cuadrado C;
      init( &C );
      int total = 0, suma = 0;
      for(suma=0; suma<=36; suma++) {
            int cantSol = 0;
            Backtracking(&C, 0, &cantSol, suma);
            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);
            total += cantSol;

      }
      printf("Total: %d", total);
      return 0;
}


O sea, antes de empezar a contar las soluciones para una determinada iteración, hay que fijar en 0 el contador. De lo contrario se van acumulando en cada resultado parcial como pasó en mi ejemplo:

Cambiando suma <= 36 por suma <= 1, la salida sería:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
-------
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 0, es: 1
0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
-------
0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0
-------
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
-------
0 0 1 0
1 0 0 0
0 1 0 0
0 0 0 1
-------
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
-------
0 1 0 0
0 0 1 0
1 0 0 0
0 0 0 1
-------
1 0 0 0
0 0 0 1
0 1 0 0
0 0 1 0
-------
1 0 0 0
0 0 1 0
0 0 0 1
0 1 0 0
-------
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 1, es: 9
Total: 10

En el for puse suma <= 36 para considerar todos los casos posibles (hasta la cuadrícula que tiene 9 en todas sus entradas).

Donde dice 9, debería ser 8 (y eso también afecta el "Total", que debiera ser 9, no 10).

Saludos.

PD. La ejecución con suma <= 36 en mi computadora tardó unos 40 minutos. Redirigí la salida estándar a un archivo de texto y resultó tener 36.550.209 líneas y ocupar 272 MB de mi disco duro. La respuesta a la pregunta

Citar
¿De cuántas maneras se puede rellenar una cuadrícula de 4x4 con los dígitos d, 0 ≤ d ≤ 9 de modo que cada fila, cada columna y las dos diagonales tienen la misma suma?

es 7.130.034 (como puedes ver, más de 7 millones).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

09 Mayo, 2015, 11:01 am
Respuesta #6

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Buenos días Luis y Pablo. Muchísimas gracias por vuestra ayuda ya que sin vosotros esto no lo hubiese conseguido la verdad. Mi problema es que yo en C soy nuevo y llevare 3 meses como mucho y por eso no tengo mucha idea de C. Se lo he enseñado a mi profesora y me ha dicho que está bien el ejercicio pero que ella lo quiere de otra forma y me lo ha puesto más complicado aún. Si no es mucha molestia, os ruego que me ayudéis porque si tal y como estaba antes el ejercicio me parecía difícil pues ahora mucho más. Si no me podéis ayudar lo entenderé y de todas formas os vuelvoa dar las gracias por todo lo que me habéis ayudado.
Os pongo aqui el ejercicio modificado por mi profesora:
Una cuadrícula de tamaño 4x4 se llena de d dígitos, 0 ≤ d ≤ 9. Se puede observar que en la cuadrícula:
6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5
 la suma de cada fila y cada columna tiene el valor 12. Por otra parte, la suma de cada diagonal es también 12.¿De cuántas maneras se puede rellenar una cuadrícula de 4x4 con los dígitos d, 0 ≤ d ≤ 9 de modo que cada fila, cada columna y las dos diagonales tienen la misma suma?
 Se pide:
• Implemente un programa en C que intente resolver este problema. La implementación del programa debe tener las siguientes características:
o Debe estar formado por tres ficheros: uno con extensión .h con las bibliotecas, las cabeceras de las funciones y las declaraciones de estructuras, variables globales (si son necesarias).Otro con extensión .c donde se almacenará la función main(). Por último debe existir otro fichero con extensión .c con todas las funciones que se vayan a utilizar.
o Al menos una de las funciones que se utilice debe ser recursiva.
o La salida se debe almacenar en un fichero “salida.txt”.
o Se debe utilizar el paso de parámetros por referencia al menos una vez en la implementación del programa.
o El programa debe ser lo más óptimo posible.
• Escriba un documento de texto cuya extensión no sea mayor de dos páginas en la que explique cómo ha realizado la implementación del programa.
  

09 Mayo, 2015, 04:11 pm
Respuesta #7

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Se pide:
• Implemente un programa en C que intente resolver este problema. La implementación del programa debe tener las siguientes características:
o Debe estar formado por tres ficheros: uno con extensión .h con las bibliotecas, las cabeceras de las funciones y las declaraciones de estructuras, variables globales (si son necesarias).Otro con extensión .c donde se almacenará la función main(). Por último debe existir otro fichero con extensión .c con todas las funciones que se vayan a utilizar.

Es inmediato a partir de mi código. La idea que a uno le surge naturalmente es hacer de Cuadrado un TAD (Tipo Abstracto de Datos) y hacer que todas las funciones que manipulaban a los Cuadrados, sean operaciones de ese TAD. A partir de eso, una reorganización del programa sería:

Cuadrado.h
#ifndef CUADRADO_H_
#define CUADRADO_H_

#include <stdio.h>

/* Definicion del TAD Cuadrado */

typedef struct _RegCuadrado Cuadrado; /* Opaco */

/* Operaciones del TAD Cuadrado */

Cuadrado *crearCuadrado();
/* Crea un Cuadrado inicializado con
 * ceros */

void destruirCuadrado(Cuadrado *C);
/* Libera la memoria de un Cuadrado */

int esValido(Cuadrado *C, int n, int S);
/* Devuelve si es valido el Cuadrado en
 * construcción hasta la posicion n,
 * siendo S la cantidad que debe sumar
 * cada una de las filas y las columnas
 * asi como las dos diagonales
 */

void actualizar(Cuadrado *C, int n);
/* Actualiza la estructura de datos C
 * cada vez que se avanza una posicion
 * en la tupla durante el backtracking
 */

void desactualizar(Cuadrado *C, int n);
/* Deshace los cambios hechos durante
 * actualizar() si se avanzo en un sentido
 * equivocado al recorrer el arbol de
 * soluciones
 */

void imprimir(Cuadrado *C, FILE *f);
/* Imprime el cuadrado C */

void Backtracking(Cuadrado *C, int n, int *cantSol, int S, FILE *f);
/* Procedimiento que realiza el backtracking
 * sobre el arbol de soluciones (que comprende
 * todas las matrices 4x4 con elementos en
 * {0,...,9}), pretendiendo encontrar las
 * cuadriculas 4x4 que cumplen que la suma
 * de cada fila, cada columna y las dos
 * diagonales es S.
 * -C      : cuadrado en construccion
 * -n      : proxima posicion a llenar en la tupla
 * -cantSol: cantidad de soluciones encontradas
 * -S      : numero que debe sumar cada fila, cada
 *           columna y las dos diagonales
 */

#endif /* CUADRADO_H_ */

[cerrar]

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) {
      int i;
      /* Chequeo filas */
      for(i=0; i<4; i++) {
            if (C->sumasFila[i] > S){
                  return 0;
            }
      }
      if( n>=4 && C->sumasFila[0] != S) { return 0; }
      else if ( n>=8 && C->sumasFila[1] != S) { return 0; }
      else if ( n>=12 && C->sumasFila[2] != S) { return 0; }

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

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

      if( n == 16 ) {
            if ( C->sumasFila[3]==S && C->sumasColumna[3]==S && C->sumaDiag1==S ) {
                  return 1;
            } else {
                  return 0;
            }
      }
      return 1;
}

void actualizar(Cuadrado *C, int n) {
      if( n==0 || n==5 || n==10 || n==15 ) {
            C->sumaDiag1 += C->tupla[n];
      } else if ( n==3 || n==6 || n==9 || n==12 ) {
            C->sumaDiag2 += C->tupla[n];
      }
      if(0 <= n && n <= 3) { C->sumasFila[0] += C->tupla[n]; }
      else if(4 <= n && n <= 7) { C->sumasFila[1] += C->tupla[n]; }
      else if(8 <= n && n <= 11) { C->sumasFila[2] += C->tupla[n]; }
      else if(12 <= n && n <= 15) { C->sumasFila[3] += C->tupla[n]; }
      C->sumasColumna[n%4] += C->tupla[n];
}

void desactualizar(Cuadrado *C, int n) {
      if( n==0 || n==5 || n==10 || n==15 ) {
            C->sumaDiag1 -= C->tupla[n];
      } else if ( n==3 || n==6 || n==9 || n==12 ) {
            C->sumaDiag2 -= C->tupla[n];
      }
      if(0 <= n && n <= 3) { C->sumasFila[0] -= C->tupla[n]; }
      else if(4 <= n && n <= 7) { C->sumasFila[1] -= C->tupla[n]; }
      else if(8 <= n && n <= 11) { C->sumasFila[2] -= C->tupla[n]; }
      else if(12 <= n && n <= 15) { C->sumasFila[3] -= 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]

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

int main(void) {
      Cuadrado *C = crearCuadrado();
      FILE *fh = fopen("salida.txt", "w");
      int total = 0, suma = 0;
      for(suma=0; suma<=36; suma++) {
            int cantSol = 0;
            Backtracking(C, 0, &cantSol, suma, fh);
            fprintf(fh, "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);
            total += cantSol;
      }
      fprintf(fh, "Total: %d", total);
      printf("Total: %d", total);
      fclose(fh);
      destruirCuadrado(C);
      return 0;
}

[cerrar]

o Al menos una de las funciones que se utilice debe ser recursiva.

Backtracking() es recursiva.

o La salida se debe almacenar en un fichero “salida.txt”.

En el último programa hice (pequeñas) modificaciones para cumplir con ese requisito.

o Se debe utilizar el paso de parámetros por referencia al menos una vez en la implementación del programa.

En C, creo que no hay manera de pasar un parámetro por referencia (siempre es por valor). La manera de simular un pasaje por referencia es pasar un puntero y en la rutina modificar el valor apuntado por dicho puntero. Si es así, eso se hace en la mayoría de las funciones que tienen Cuadrado *C como argumento.

o El programa debe ser lo más óptimo posible.

Este programa no es óptimo, y hay bastantes cosas para mejorar su eficiencia; especialmente en la función

int esValido(Cuadrado *C, int n, int S);

Básicamente, cuando se llega hasta la posición n, ya se sabe que los valores hasta n son válidos, por lo que no tiene sentido chequear nuevamente su validez como hace mi función. Sería más razonable chequear solamente el resto de la tupla, es decir de n en adelante. Se ahorrarían así un montón de comparaciones y seguro el programa terminaría más rápido. Aparte, está implementada de forma tan horripilante que resulta obscena. Lo dejo para que lo corrijas tú.

• Escriba un documento de texto cuya extensión no sea mayor de dos páginas en la que explique cómo ha realizado la implementación del programa.

Esto es por lejos lo más importante: el contenido. Lo demás es la forma, y cambia totalmente de un lenguaje de programación a otro. Yo que tú me preocuparía por entender por qué funciona este programa. Y no sé si lo tienes 100% claro.

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

09 Mayo, 2015, 06:17 pm
Respuesta #8

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Al ejecutar el programa anterior, obtuve:

La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 0, es: 1
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 1, es: 8
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 2, es: 48
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 3, es: 200
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 4, es: 675
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 5, es: 1904
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 6, es: 4736
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 7, es: 10608
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 8, es: 21925
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 9, es: 42328
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 10, es: 76976
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 11, es: 131320
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 12, es: 209127
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 13, es: 309968
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 14, es: 427440
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 15, es: 549184
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 16, es: 658457
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 17, es: 736744
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 18, es: 766736
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 19, es: 736744
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 20, es: 658457
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 21, es: 549184
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 22, es: 427440
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 23, es: 309968
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 24, es: 209127
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 25, es: 131320
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 26, es: 76976
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 27, es: 42328
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 28, es: 21925
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 29, es: 10608
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 30, es: 4736
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 31, es: 1904
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 32, es: 675
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 33, es: 200
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 34, es: 48
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 35, es: 8
La cantidad total de cuadriculas 4 x 4 cumpliendo que la suma de cada fila, cada columna y las dos diagonales es 36, es: 1
Total: 7130034

Nota la simetría que hay en relación a la línea marcada en negrita. Esto es porque, por ejemplo, si en

0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
-------
0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0
-------
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
-------
0 0 1 0
1 0 0 0
0 1 0 0
0 0 0 1
-------
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
-------
0 1 0 0
0 0 1 0
1 0 0 0
0 0 0 1
-------
1 0 0 0
0 0 0 1
0 1 0 0
0 0 1 0
-------
1 0 0 0
0 0 1 0
0 0 0 1
0 1 0 0

sustituimos los 0s por 9s y los 1s por 8s, obtenemos

9 9 9 8
9 8 9 9
8 9 9 9
9 9 8 9
-------
9 9 9 8
8 9 9 9
9 9 8 9
9 8 9 9
-------
9 9 8 9
9 8 9 9
9 9 9 8
8 9 9 9
-------
9 9 8 9
8 9 9 9
9 8 9 9
9 9 9 8
-------
9 8 9 9
9 9 9 8
9 9 8 9
8 9 9 9
-------
9 8 9 9
9 9 8 9
8 9 9 9
9 9 9 8
-------
8 9 9 9
9 9 9 8
9 8 9 9
9 9 8 9
-------
8 9 9 9
9 9 8 9
9 9 9 8
9 8 9 9

que son las cuadrículas que se obtienen para cuando suma es 35. En general, la cantidad de matrices que se obtienen para cuando suma es igual a \( i \), es la misma que la cantidad de matrices que se obtienen para cuando suma es igual a \( 36-i \) y esto para todo \( i\in \{0,\dots,17\} \). Además, las segundas se obtienen a partir de las primeras, sustituyendo cada dígito \( d \) por \( 9-d \).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

12 Mayo, 2015, 01:22 pm
Respuesta #9

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por todo Pablo. ¿Te importaría decirme tu whatsapp para hablar contigo respecto del trabajo para las dudas que tengo? y así podemos hablar mejor que por este foro.
Gracias.

12 Mayo, 2015, 06:03 pm
Respuesta #10

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por todo Pablo. ¿Te importaría decirme tu whatsapp para hablar contigo respecto del trabajo para las dudas que tengo?

Mi celular es un Sony Ericsson K310 que uso desde el 2007 (como verás, un poco antiguo), por lo que no uso whatsapp. Y en caso de tener uno moderno, tampoco usaría whatsapp sino Telegram. Además prefiero IRC a cualquier protocolo de mensajería instantánea.

así podemos hablar mejor que por este foro.

Este foro soporta \( \LaTeX \) y hasta insertar html con etiquetas [html][/html]. Lo único que le haría falta es algo como [sourcecode language="C"][/code] que soporte syntax highlighting, pero en cualquier caso es mucho más avanzado que la comunicación en texto plano que ofrece whatsapp (o cualquier otro similar).

Además de eso, violaría las normas del foro proporcionarte ayuda en privado; piensa que en el futuro puede haber otras personas interesadas en este problema a las que les podrían servir las respuestas a tus preguntas.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

12 Mayo, 2015, 06:49 pm
Respuesta #11

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Vale sin problemas. Pues los problemas que tengo son:
- que mi profesora me ha dicho que tupla no lo hemos dado que lo haga de otra forma entonces he pensado en hacerlo con matrices pero no se hacerlo...
- las librerias y variables globales que pusistes no se para que sirven. Voy a enviar tal y como lo tengo yo ahora mismo. Dime que variables globales me faltan o que librerias me faltan porfavor.
Gracias por todo.
#include <stdio.h>
#include <stdlib.h>

/* Definición de la estructura de la matriz */

typedef struct Cuadricula Matriz;

/* Operaciones de la matriz */

Matriz *crearMatriz();
/* Crea una matriz inicializada con ceros */

void destruirMatriz(Matriz *M);
/* Libera la memoria de una matriz */

int esValido(Matriz *M, int n, int S);
/* Devuelve si es valido la matriz en
 * construcción hasta la posicion n,
 * siendo S la cantidad que debe sumar
 * cada una de las filas y las columnas
 * asi como las dos diagonales
 */

void actualizar(Matriz *M, int n);
/* Actualiza la estructura de datos M
 * cada vez que se avanza una posicion
 * en la tupla durante el backtracking
 */

void desactualizar(Matriz *M, int n);
/* Deshace los cambios hechos durante
 * actualizar() si se avanzo en un sentido
 * equivocado al recorrer el arbol de
 * soluciones
 */

void imprimir(Matriz *M, FILE *f);
/* Imprime la matriz M */

void Backtracking(Matriz *M, int n, int *cantSol, int S, FILE *f);
/* Procedimiento que realiza el backtracking
 *sobre el arbol de soluciones (que comprende
 * todas las matrices 4x4 con elementos en
 * {0,...,9}), pretendiendo encontrar las
 * cuadriculas 4x4 que cumplen que la suma
 * de cada fila, cada columna y las dos
 * diagonales es S.
 * -M      : matriz en construccion
 * -n      : proxima posicion a llenar en la tupla
 * -cantSol: cantidad de soluciones encontradas
 * -S      : numero que debe sumar cada fila, cada
 *           columna y las dos diagonales
 */

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

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

void destruirMatriz(Matriz *M)
{
      free(M);
}

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;
        }
      if( n == 16 )
        {
            if ( M->sumasFila[3]==S && M->sumasColumna[3]==S && M->sumaDiag1==S )
            {
                  return 1;
            } else
            {
                  return 0;
            }
        }
      return 1;
}

void actualizar(Matriz *M, int n)
{
      if( n==0 || n==5 || n==10 || n==15 )
        {
            M->sumaDiag1 += M->tupla[n];
        } else if ( n==3 || n==6 || n==9 || n==12 )
        {
            M->sumaDiag2 += M->tupla[n];
        }
      if(0 <= n && n <= 3)
      {
          M->sumasFila[0] += M->tupla[n];
      }
      else if(4 <= n && n <= 7)
        {
            M->sumasFila[1] += M->tupla[n];
        }
      else if(8 <= n && n <= 11)
        {
            M->sumasFila[2] += M->tupla[n];
        }
      else if(12 <= n && n <= 15)
        {
            M->sumasFila[3] += M->tupla[n];
        }
      M->sumasColumna[n%4] += M->tupla[n];
}

void desactualizar(Matriz *M, int n)
{
      if( n==0 || n==5 || n==10 || n==15 )
        {
            M->sumaDiag1 -= M->tupla[n];
        } else if ( n==3 || n==6 || n==9 || n==12 )
        {
            M->sumaDiag2 -= M->tupla[n];
        }
      if(0 <= n && n <= 3)
      {
           M->sumasFila[0] -= M->tupla[n];
      }
      else if(4 <= n && n <= 7)
        {
             M->sumasFila[1] -= M->tupla[n];
        }
      else if(8 <= n && n <= 11)
        {
             M->sumasFila[2] -= M->tupla[n];
        }
      else if(12 <= n && n <= 15)
        {
             M->sumasFila[3] -= M->tupla[n];
        }
      M->sumasColumna[n%4] -= M->tupla[n];
}

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

void Backtracking(Matriz *M, int n, int *cantSol, int S, FILE *f)
{
      int k;
      if ( esValido(M, n, S) )
        {
            if( n == 16 )
            {
                  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;
                  }
            }
        }
}
int main(void)
{
      Matriz *M = crearMatriz();
      FILE *fp = fopen("salida.txt", "w");
      int total1 = 0,total2=0,total=0, suma = 0;
// El máximo de la suma es 36 ya que el número máximo es 9 y hay 4 posiciones,luego 9x4=36.
//Al estar haciendo el trabajo me he dado cuenta que las soluciones son simétricas ya que:
//Cuando la suma es 0 o 36 hay 1 única manera, cuando es 1 o 35 hay 8 maneras, cuando hay 2 o 34 hay 48 maneras...así hasta cuando la suma es 18 que hay 766736 maneras.
//Luego para que el programa vaya más rapido lo he calculado solo hasta suma=18. Primero he multiplicado por 2 desde suma=0 hasta suma=17 y despues le he sumado la suma=18.
      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;

      fprintf(fp, "Total: %d", total=total1+total2);
      printf("Total: %d", total);
      fclose(fp);
      destruirMatriz(M);
      return 0;
}

13 Mayo, 2015, 12:44 pm
Respuesta #12

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Por favor decirme como puedo hacer lo que envie ayer pero en vez de con tupla[16] con una matriz[4][4].
Espero vuestra respuesta.
Gracias.

13 Mayo, 2015, 04:44 pm
Respuesta #13

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Por favor decirme como puedo hacer lo que envié ayer pero en vez de con tupla[16] con una matriz[4][4].

El struct que definiste quedaría así:

struct Cuadricula
{
      int matriz[4][4];
      int sumasFila[4];
      int sumasColumna[4];
      int sumaDiag1, sumaDiag2;
};


Debes reimplementar las operaciones para que actúen sobre esta nueva estructura. También en el método Backtracking() necesitarás una función que dado n en 0..15 te devuelva la posición en la matriz correspondiente. O de lo contrario puedes modificar la firma de Backtracking() para que en vez de pasar n, pases dos parámetros i,j con la fila y la columna de la nueva posición a llenar (aunque me parece más fácil lo primero).

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

21 Mayo, 2015, 04:25 pm
Respuesta #14

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Buenas tardes, he estado pensando desde el fin de semana como puedo hacer el ejercicio con las matrices pero no soy capaz, solo he conseguido poner el struct y crear la matriz pero todo lo demás no se como ponerlo en forma de matriz. Por favor ayudarme con este ejercicio. Gracias por adelantado.
Os lo dejo tal y como lo tengo yo ahora mismo.

#include <stdio.h>
#include <stdlib.h>

/* Definición de la estructura de la matriz */

typedef struct Cuadricula Matriz;

/* Operaciones de la matriz */

Matriz *crearMatriz();
/* Crea una matriz inicializada con ceros */

void destruirMatriz(Matriz *M);
/* Libera la memoria de una matriz */

int esValido(Matriz *M, int n, int S);
/* Devuelve si es valido la matriz en
 * construcción hasta la posicion n,
 * siendo S la cantidad que debe sumar
 * cada una de las filas y las columnas
 * asi como las dos diagonales
 */

void actualizar(Matriz *M, int n);
/* Actualiza la estructura de datos M
 * cada vez que se avanza una posicion
 * en la tupla durante el backtracking
 */

void desactualizar(Matriz *M, int n);
/* Deshace los cambios hechos durante
 * actualizar() si se avanzo en un sentido
 * equivocado al recorrer el arbol de
 * soluciones
 */

void imprimir(Matriz *M, FILE *f);
/* Imprime la matriz M */

void Backtracking(Matriz *M, int n, int *cantSol, int S, FILE *f);
/* Procedimiento que realiza el backtracking
 *sobre el arbol de soluciones (que comprende
 * todas las matrices 4x4 con elementos en
 * {0,...,9}), pretendiendo encontrar las
 * cuadriculas 4x4 que cumplen que la suma
 * de cada fila, cada columna y las dos
 * diagonales es S.
 * -M      : matriz en construccion
 * -n      : proxima posicion a llenar en la tupla
 * -cantSol: cantidad de soluciones encontradas
 * -S      : numero que debe sumar cada fila, cada
 *           columna y las dos diagonales
 */

struct Cuadricula
{
      int m[4][4];
      int sumasFila[4];
      int sumasColumna[4];
      int sumaDiag1, sumaDiag2;
};

Matriz *crearMatriz()
{
      Matriz *M = malloc(sizeof(Matriz));
      int k,i;
      for(k=0; k<4; k++)
      {
           for(i=0;i<4;i++)
           {
               M->m[k][i] = 0;
           }
      }
      for(k=0; k<4; k++)
      {
            M->sumasFila[k] = 0;
            M->sumasColumna[k] = 0;
      }
      M->sumaDiag1 = 0;
      M->sumaDiag2 = 0;
      return M;
}

void destruirMatriz(Matriz *M)
{
      free(M);
}

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;
        }
      if( n == 16 )
        {
            if ( M->sumasFila[3]==S && M->sumasColumna[3]==S && M->sumaDiag1==S )
            {
                  return 1;
            } else
            {
                  return 0;
            }
        }
      return 1;
}

void actualizar(Matriz *M, int n)
{
      if( n==0 || n==5 || n==10 || n==15 )
        {
            M->sumaDiag1 += M->tupla[n];
        } else if ( n==3 || n==6 || n==9 || n==12 )
        {
            M->sumaDiag2 += M->tupla[n];
        }
      if(0 <= n && n <= 3)
      {
          M->sumasFila[0] += M->tupla[n];
      }
      else if(4 <= n && n <= 7)
        {
            M->sumasFila[1] += M->tupla[n];
        }
      else if(8 <= n && n <= 11)
        {
            M->sumasFila[2] += M->tupla[n];
        }
      else if(12 <= n && n <= 15)
        {
            M->sumasFila[3] += M->tupla[n];
        }
      M->sumasColumna[n%4] += M->tupla[n];
}

void desactualizar(Matriz *M, int n)
{
      if( n==0 || n==5 || n==10 || n==15 )
        {
            M->sumaDiag1 -= M->tupla[n];
        } else if ( n==3 || n==6 || n==9 || n==12 )
        {
            M->sumaDiag2 -= M->tupla[n];
        }
      if(0 <= n && n <= 3)
      {
           M->sumasFila[0] -= M->tupla[n];
      }
      else if(4 <= n && n <= 7)
        {
             M->sumasFila[1] -= M->tupla[n];
        }
      else if(8 <= n && n <= 11)
        {
             M->sumasFila[2] -= M->tupla[n];
        }
      else if(12 <= n && n <= 15)
        {
             M->sumasFila[3] -= M->tupla[n];
        }
      M->sumasColumna[n%4] -= M->tupla[n];
}

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

void Backtracking(Matriz *M, int n, int *cantSol, int S, FILE *f)
{
      int k;
      if ( esValido(M, n, S) )
        {
            if( n == 16 )
            {
                  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;
                  }
            }
        }
}
int main(void)
{
      Matriz *M = crearMatriz();
      FILE *fp = fopen("salida.txt", "w");
      int total1 = 0,total2=0,total=0, suma = 0;
// El máximo de la suma es 36 ya que el número máximo es 9 y hay 4 posiciones,luego 9x4=36.
//Al estar haciendo el trabajo me he dado cuenta que las soluciones son simétricas ya que:
//Cuando la suma es 0 o 36 hay 1 única manera, cuando es 1 o 35 hay 8 maneras, cuando hay 2 o 34 hay 48 maneras...así hasta cuando la suma es 18 que hay 766736 maneras.
//Luego para que el programa vaya más rapido lo he calculado solo hasta suma=18. Primero he multiplicado por 2 desde suma=0 hasta suma=17 y despues le he sumado la suma=18.
      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;

      fprintf(fp, "Total: %d", total=total1+total2);
      printf("Total: %d", total);
      fclose(fp);
      destruirMatriz(M);
      return 0;
}

25 Mayo, 2015, 01:57 am
Respuesta #15

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo pepeluromero, disculpa por la demora.

Buenas tardes, he estado pensando desde el fin de semana como puedo hacer el ejercicio con las matrices pero no soy capaz, solo he conseguido poner el struct y crear la matriz pero todo lo demás no se como ponerlo en forma de matriz.

Me parece extraño que no hayas podido hacerlo. Lo único que se me ocurre es que no hayas entendido la semántica de tupla. Se trata de un arreglo de 16 elementos donde los índices 0..3 corresponden a la primer fila de la matriz, 4..7 a la segunda fila de la matriz, 8..11 a la tercera y 12..15 a la cuarta. A partir de eso debiera ser inmediata la adaptación de mi programa a la nueva estructura m[4][4]. Dime qué dudas concretas te surgen.

Lo que me parece más delicado es esto,

Debes reimplementar las operaciones para que actúen sobre esta nueva estructura. También en el método Backtracking() necesitarás una función que dado n en 0..15 te devuelva la posición en la matriz correspondiente. O de lo contrario puedes modificar la firma de Backtracking() para que en vez de pasar n, pases dos parámetros i,j con la fila y la columna de la nueva posición a llenar (aunque me parece más fácil lo primero).

o sea, cómo solucionamos ese problema. Observa que dado \( n\in \{0,1,\dots,15\} \), la fila correspondiente la puedes obtener como parte entera de \( n/4 \) y la columna, como el resto de dividir \( n \) entre 4.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

27 Mayo, 2015, 01:45 pm
Respuesta #16

pepeluromero

  • Junior
  • Mensajes: 32
  • Karma: +0/-0
  • Sexo: Masculino
Al final me han dejado hacerlo con tuplas :).
Pablo, ¿por qué pones
 if( n == 16 )
        {
            if ( M->sumasFila[3]==S && M->sumasColumna[3]==S && M->sumaDiag1==S )
            {
                  return 1;
            } else
            {
                  return 0;
            }
        }
si la n de la tupla va desde el 0 hasta el 15?

27 Mayo, 2015, 07:33 pm
Respuesta #17

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Cuando ya se ha completado toda la matriz se llama a la función Backtracking() con n igual a 16. En esa situación, la matriz ya está completa pero resta chequear que el último elemento que fue completado (el de la fila 4 y columna 4) haga que:

  • La suma de los elementos de la última fila sea S.

  • La suma de los elementos de la última columna sea S.

  • La suma de los elementos de la diagonal secundaria principal sea S.

En ese caso, la función esValido(M, n, S) es llamada con n igual a 16 y tiene que retornar verdadero si y sólo si se cumplen simultáneamente esas tres condiciones citadas anteriormente. Observa también toda la cantidad de chequeos innecesarios que hace esValido(M, n, S) cuando n es 16 antes de llegar a ese trozo de código que citas (esto es lo que te comentaba de que esta solución puede hacerse aún bastante más eficiente).



Para saber si lo entendiste, contéstame esto:

Al final me han dejado hacerlo con tuplas :).
Pablo, ¿por qué pones
 if( n == 16 )
        {
            if ( M->sumasFila[3]==S && M->sumasColumna[3]==S && M->sumaDiag1==S )
            {
                  return 1;
            } else
            {
                  return 0;
            }
        }
si la n de la tupla va desde el 0 hasta el 15?

¿Qué pasaría si eliminaras esas líneas?  ;)

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

28 Mayo, 2015, 08:47 am
Respuesta #18

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Probablemente, quede más claro así: primero borramos el código que citas de esValido() y luego agregamos una operación al TAD que sea

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


De esta manera, Backtracking() queda más elegante:

void Backtracking(Cuadrado *C, int n, int *cantSol, int S, FILE *f) {
      int k;
      if ( esValido(C, n, S) ) {
            if( esSolucion(C, n, S) ) {
                  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;
                  }
            }
      }
}
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

01 Junio, 2015, 11:57 am
Respuesta #19

pepeluromero

  • Junior
  • Mensajes: 32
  • 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()