1

Hola Quiero elaborar un cuadrado mágico de 3 x 3 en C utilizando backtracking (como en el ejercicio de las 4 reinas) con recursividad.

Además debo de ingresar el valor máximo que tendrá dentro este cuadrado mágico, por ejemplo si ingreso m = 26, mi cuadro debería quedar algo así:

introducir la descripción de la imagen aquí

como debe ser realizado por backtracking, esa es una posible solución de muchas, actualmente tengo un código simple de 3 loops para realizar todas las combinaciones posibles ingresando el valor de M.

adjunto código:

#include<stdio.h>
#include<string.h>
#define N 10

void print(int *num, int n)
{
    int i;
    for ( i = 0 ; i < n ; i++)
        printf("%d ", num[i]);
    printf("\n");
}

int main()
{
    int num[N];
    int *ptr;
    int temp;
    int i, m, j;
    int n = 3;
    printf("\nlimite: ");
        scanf("%d", &m);
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int k = 1; k <= m; ++k)
            {
                permutaciones ++;
                printf("%i,%i,%i\n", i,j,k);
            }
        }
    }
    return 0;
}

¿como puedo transformar este código para que sea de manera recursiva ? y sin repetir los primeros valores, por ejemplo [1,1,1][16,16,16] ya que esto me permitirá crear las posibles filas y columnas posibles para elaborar el cuadro mágico.

y finalmente poder imprimir todas las soluciones posibles que sean correctas. introducir la descripción de la imagen aquí

para la compilación utilizo MingGW - gcc en windows, de antemano muchas gracias por la ayuda

3
  • ¿? Dejando aparte que simplemente estás pidiendo "dadme el código recursivo", está la divertida cuestión de que el código iterativo que muestras de base no resuelve el problema descrito, tu código solo imprime filas con las variaciones con repetición entre 1 y m tomadas de tres en tres. En ningún momento intentas crear un cuadrado mágico. La regla de "muestra lo que has hecho" no significa "escribe cualquier porquería para que parezca que has hecho algo". TIENES QUE INTENTAR RESOLVER EL PROBLEMA EN SERIO Y NO PEDIR QUE TE ESCRIBAMOS EL EJERCICIO PARA TÍ.
    – SJuan76
    Commented el 14 sept. 2020 a las 8:58
  • describí el problema, pero jamas he pedido que "me den el código", solo necesitaba que me orientaran en como podía quedar el código de mis 3 FOR de manera recursiva, pero no te molestes que ya lo solucione Por mi mismo Commented el 14 sept. 2020 a las 11:39
  • Por favor, publica tu solución.
    – Candid Moe
    Commented el 14 sept. 2020 a las 12:49

2 respuestas 2

2

Para estos efectos consideramos que dos cuadrados mágicos son idénticos si su suma es la misma.

Que dos cuadrados mágicos sean idénticos significa que se puede pasar de uno a otro intercambiando columnas, filas o rotando todo el cuadrado.

Entonces, estos ocho cuadrados mágicos son idénticos, y mi solución imprimira solo uno de ellos:

introducir la descripción de la imagen aquí

A efectos de simplificar la discusión, trabajare sobre datos fijos:

#define N 9
#define LIMITE 26
int num[LIMITE];
int sumas[LIMITE * 3];

El arreglo num contiene todos los digitos desde 1 a LIMITE. Los primeros 9 valores corresponde a los 9 casilleros del cuadrado magico.

El arreglo sumas se usa para registrar los valores ya calculados. Si sumas[x] == x, significa que ya se encontró un cuadrado mágico con suma x.

El procedimiento recursivo hacer_magia recibe como parámetro el indice 0-8 del casillero que debemos ajustar, y prueba todos los cuadrados producidos al intercambiar el casillero en cuestión con cada uno de los valores que siguen, hasta el último elemento de la lista (que en este caso tiene 26 elementos).

Para probar los cuadrados, el procedimiento se llama a si mismo pasando el indice del siguiente casillero.

Cuando la recursión alcanza al último casillero, se evalúa el cuadrado y se imprime si es mágico:

/*
 * Crea un cuadrado magico de 3x3
 * 
 * int idx_num: Indice entre 0-8 que da el casillero desde el
 * cual llenar la matriz.
 *  
 */
void hacer_magia(int idx_num) {

    //  Hack para acortar la busqueda: si la primera fila da un valor
    //  ya calculado, desechamos la matriz, pues es mera reflexion/rotacion
    //  de una matriz previa.
    
    if (idx_num > 2) {
        int s0 = suma_fila(0);
        if (ya_calculada(s0)) {
            //  Desechamos la matriz.
            return;
            }
        else if (idx_num < 6) {
            //  Otro hack. Si las dos primeras filas no coinciden (estando completas)
            //  no tiene caso seguir. Si la segunda fila es mayor que la primera,
            //  tampoco.
            int s1 = suma_fila(1);
            if ((idx_num == 3 && s1 > s0) ||
                    (idx_num == 5 && s0 != s1)) {
                return;
            }
        }
    }

    //  Estamos ante un potencial cuadrado magico.
    if (idx_num == N) {
        //  Completamos nueve casilleros, evaluar el resultado.
        if (es_magico()) {
            print(num, N);
        }
    } else {
        //  Revisar los casilleros que siguen, por si alguno forma
        //  un cuadrado magico
        hacer_magia(idx_num + 1);
        //  Intercambiar el casillero actual con cada uno de los casilleros
        //  siguientes, y evaluar en cada caso si hay cuadrados magicos.
        for (int idx_nvo = idx_num + 1; idx_nvo < LIMITE; idx_nvo++) {
            intercambiar(idx_num, idx_nvo);
            hacer_magia(idx_num + 1);
            intercambiar(idx_num, idx_nvo);
        }
    }
}

int main() {

    for (int i = 0; i < LIMITE; i++)
        num[i] = i + 1;

    hacer_magia(0);

    return 0;
}

Nota: El código completo está en Try it online!.

Aqui ocupamos varias funciones cortas, que no incluyo para no alargar la historia, pero que son simples de implementar:

  • ya_calculada(suma). Retorna 1 si ya hay un cuadrado con esa suma.
  • suma_fila(fila). Retorna la suma para la fila 0-2.
  • es_magico(). Retorna 1 si es un cuadrado mágico.
  • print(num,N). Imprime la matriz.
  • intercambiar(i1,i2). Intercambia los valores num[i1] con num[i2].

Comprobación

Cuadrado 1
   2    4    9   (15)
   6    8    1   (15)
   7    3    5   (15)
---------------
  15   15   15   (15)

Cuadrado 2
   2    4   10   (16)
   6    9    1   (16)
   8    3    5   (16)
---------------
  16   16   16   (16)

Cuadrado 3
   2    4   11   (17)
   6   10    1   (17)
   9    3    5   (17)
---------------
  17   17   17   (17)

Cuadrado 4
   2    4   12   (18)
   6   11    1   (18)
  10    3    5   (18)
---------------
  18   18   18   (18)


....

Cuadrado 41
   8   21   26   (55)
  25   24    6   (55)
  22   10   23   (55)
---------------
  55   55   55   (55)

RUN FINISHED; exit value 0; real time: 1m 28s; user: 0ms; system: 1m 28s
0
0

Exactamente Candid Moe, nos dará los diferentes cuadrados mágicos posibles, pero para ser un cuadrado mágico completo se deben considerar ambas diagonales por lo que, con ese código y considerando limite = 12, este nos generará 10 cuadros mágicos.

ahora agregando el metodo para comprobrar la otra diagonal:

int suma_diagonalIzq() {
    int suma = 0;
    for (int i = DIM - 1, j = 0; i >= 0 && j < DIM; --i, ++j) {
        suma += num[i * DIM + j];
    }
    return suma;
}

y adicionando debajo del código suma_diagonal()

if (magico == suma) {
    suma = suma_diagonalIzq();
}

con esto podremos obtener solo 3 cuadros mágicos posibles teniendo como limite = 12, pero todas las sumas serán iguales.

Agradezco tu ayuda y aporte del código y espero que tu gran aporte y esta pequeña parte adicionada les se útil a muchos

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.