Autor Tema: Criss Cross en C

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

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

pepeluromero

  • $$\Large \color{#6a84c0}\pi$$
  • 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,447
  • 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

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 303
  • 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,447
  • 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,447
  • 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,447
  • 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

  • $$\Large \color{#6a84c0}\pi$$
  • 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,447
  • 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,447
  • 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

  • $$\Large \color{#6a84c0}\pi$$
  • 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.