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,447
  • 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

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

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

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

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

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