Cómo resolver un rompecabezas de cuadrado mágico de 3×3 en C y Python

¿Qué es un cuadrado mágico?

Un cuadrado mágico es una matriz cuadrada con una disposición especial de los números. Los valores se colocan de tal manera que la suma de cada fila, cada columna y ambas diagonales principales permanece constante. Los cuadrados mágicos son sencillos rompecabezas de lógica que se utilizan en matemáticas recreativas.

Ejemplo de cuadrados mágicos:

El diagrama anterior muestra un cuadrado mágico de orden 3. La suma de cada diagonal, fila y columna es igual a 15. La siguiente sección explica cómo se obtiene este total constante.

Cómo funcionan los cuadrados mágicos

Un cuadrado mágico de orden n es una matriz de n x n que contiene n² enteros positivos. El número de filas o columnas se denomina orden de la matriz.

Los rompecabezas de cuadrados mágicos típicos tienen un orden impar y utilizan los números enteros del 1 al n². Dado que la suma de cada fila, columna y diagonal debe ser la misma, ese valor se denomina suma mágica o constante mágica. La constante depende únicamente de n. La fórmula para la suma mágica de orden n es:

Consideremos un cuadrado mágico de orden 3. La suma mágica es entonces:

Esta fórmula explica la aritmética, pero el enigma tiene una larga historia cultural que le da su nombre memorable.

¿Por qué se les llama magia?

Los matemáticos de la antigüedad estaban fascinados por las combinaciones interesantes de números, y el cuadrado mágico era una de ellas. La evidencia más antigua data de China, alrededor del año 190 a. C.

Los estudios demuestran la existencia de cuadrados mágicos en el antiguo Japón, India y Arabia. Las leyendas vinculaban estas configuraciones con el mundo mágico, y el nombre perduró. Más allá del folclore, los matemáticos también han definido categorías formales que distinguen un cuadrado de otro.

Tipos de cuadrado mágico

En matemáticas existen varias variantes de cuadrados mágicos:

• Cuadrado Mágico Normal: Contiene los primeros n² números naturales.
• Cuadrado Semi-Mágico: Solo las filas y las columnas suman la constante mágica.
• Cuadrado Mágico Sencillo: Las filas, las columnas y ambas diagonales principales suman la constante mágica.
• El cuadrado mágico más perfecto: Un cuadrado mágico normal con dos propiedades adicionales. Cada subcuadrado de 2x2 de la matriz suma 2(n²+1), y cualquier par de números que estén separados por n/2 celdas suman n²+1.

Existen más categorías basadas en propiedades adicionales. En este tutorial, cuando se utiliza el término "cuadrado mágico" sin ninguna especificación, se refiere a un cuadrado mágico simple, normal y de orden impar.

Algoritmo para generar un cuadrado mágico

El algoritmo clásico para generar un cuadrado mágico de orden impar, llamado método siamés, es el siguiente:

• El primer número (1) se almacena en la posición (n/2, n-1), donde la primera coordenada es el índice de fila y la segunda es el índice de columna. Para los pasos posteriores, esta posición se denominará (x, y).
• El siguiente número se coloca en (x-1, y+1). Si esa posición no es válida, aplique las siguientes reglas:
  1. Si el índice de fila es -1, ajústelo a n-1. Si el índice de columna es n, ajústelo a 0.
  2. Si la posición calculada ya contiene un número, incremente la fila en 1 y disminuya la columna en 2.
  3. Si la fila es -1 y la columna es n al mismo tiempo, la nueva posición es (0, n-2).

Nota: Este algoritmo solo genera cuadrados mágicos válidos de orden impar. El resultado es un cuadrado mágico normal que contiene los primeros n² números naturales. Puede haber más de una solución válida para el mismo n.

Las reglas se aclaran con un pequeño ejemplo del orden 3, que utiliza los números del 1 al 9.

Cómo funciona en un cuadrado de 3 por 3

Aplicando el algoritmo Arriba se detallan los pasos:

Paso 1) El primer número (1) se coloca en (3/2, 3-1) o (1, 2). Para los pasos siguientes, se establece x = 1 e y = 2.

Paso 2) Las posiciones de los números restantes se calculan de la siguiente manera.

Posición del número 2:

El siguiente número debería ir a (x-1, y+1) o (0, 3), que no es una posición válida. Según la regla (a), la columna vuelve a 0, lo que da (0, 0). Establecemos x = 0, y = 0.

Posición del número 3:

El número 3 debería estar en (x-1, y+1) o (-1, 1), lo cual no es una posición válida. Según la regla (a), la fila se reinicia en n-1 (que es 2). Por lo tanto, el número 3 va a (2, 1). Establecemos x = 2, y = 1.

Posición del número 4:

El número 4 debería estar en (x-1, y+1) o (1, 2), lo cual es válido pero ya contiene 1. Según la regla (b), la nueva posición es (1+1, 2-2) o (2, 0). Establecemos x = 2, y = 0.

Posición del número 5:

El número 5 debe estar en (x-1, y+1) o (1, 1), que es una posición vacía válida. Establezca x = 1, y = 1.

Posición del número 6:

El número 6 debe estar en (x-1, y+1) o (0, 2), que es una posición vacía válida. Establezca x = 0, y = 2.

Posición del número 7:

El número 7 debería estar en (x-1, y+1) o (-1, 3), lo cual no es válido. Según la regla (c), la nueva posición es (0, n-2) o (0, 1). Establecemos x = 0, y = 1.

Posición del número 8:

El número 8 debería estar en (x-1, y+1) o (-1, 2), lo cual no es válido. Según la regla (a), la fila vuelve a 2, lo que da (2, 2). Establecemos x = 2, y = 2.

Posición del número 9:

El número 9 debería estar en (x-1, y+1) o (1, 3), lo cual no es válido. Según la regla (a), la columna vuelve a 0, dando como resultado (1, 0).

Con cada celda rellena, la misma lógica se traduce directamente en pseudocódigo.

Pseudocódigo para el cuadrado mágico

Begin
    Declare an array of size n*n
    Initialize the array to 0
    Set row = n/2
    Set column = n-1
    For all number i: from 1 to n*n
        If the row = -1 and column = n
            row = 0
            column = n-2
        Else
            If row = -1
                row = n-1
            If column = n
                column = 0
        If the position already contains a number
            decrement column by 2
            increment row by 1
            continue until the position is not 0
        Else
            put the number i into the calculated position
            increment i
        Increment column value
        Decrement row value
End

El pseudocódigo se corresponde directamente con los lenguajes compilados e interpretados, que se muestran a continuación. C++ y Python.

C++ Code para el cuadrado mágico

Entrada:

/*
A C/C++ program for generating odd order magic squares
*/
#include <bits/stdc++.h>
using namespace std;

void GenerateMagicSquare(int n)
{
    int magic[n][n];
    //initializing the array
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            magic[i][j] = 0;
    //setting row and column value
    int i = n / 2;
    int j = n - 1;
    for (int k = 1; k <= n * n;)
    {
        //checking condition (c)
        if (i == -1 && j == n)
        {
            j = n - 2;
            i = 0;
        }
        else
        {
            //checking condition (a)
            if (j == n)
                j = 0;
            if (i < 0)
                i = n - 1;
        }
        //checking condition (b)
        if (magic[i][j])
        {
            j -= 2;
            i++;
            continue;
        }
        else
        {
            //placing the number into the array
            magic[i][j] = k;
            k++;
        }
        //for the next number setting (i-1, j+1)
        j++;
        i--;
    }
    //printing the matrix
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << magic[i][j] << "  ";
        cout << endl;
    }
}
int main()
{
    //This code works for only odd numbers
    int n = 7;
    cout<<"The magic sum is " << n*(n*n+1)/2 <<endl;
    GenerateMagicSquare(n);
    return 0;
}

Salida del ejemplo:

The magic sum is 175

20  12  4  45  37  29  28
11  3  44  36  35  27  19
2  43  42  34  26  18  10
49  41  33  25  17  9  1
40  32  24  16  8  7  48
31  23  15  14  6  47  39
22  21  13  5  46  38  30

El Python La versión que aparece a continuación utiliza las mismas reglas de filas y columnas.

Python Code para el cuadrado mágico

def GenerateMagicSquare(n):
    #initializing the array
    magic = [[0 for x in range(n)]
                for y in range(n)]
    #setting row and column value
    i = n // 2
    j = n - 1
    k = 1
    while k <= (n * n):
        #checking condition (c)
        if i == -1 and j == n:
            j = n - 2
            i = 0
        else:
            #checking condition (a)
            if j == n:
                j = 0
            if i < 0:
                i = n - 1
        #checking conditon (b)
        if magic[i][j]:
            j = j - 2
            i = i + 1
            continue
        else:
            #placing the number into the array
            magic[i][j] = k
            k = k + 1
        #for the next number setting (i-1, j+1)
        j = j + 1
        i = i - 1
    #printing the matrix
    for i in range(0, n):
        for j in range(0, n):
            print('%2d ' % (magic[i][j]),end='')
            if j == n - 1:
                print()
#This code works for only odd numbers
n = 7
print("The magic sum is ",n * (n * n + 1) // 2, "\n")
GenerateMagicSquare(n)

Salida del ejemplo:

The magic sum is  175

20 12  4 45 37 29 28
11  3 44 36 35 27 19
 2 43 42 34 26 18 10
49 41 33 25 17  9  1
40 32 24 16  8  7 48
31 23 15 14  6 47 39
22 21 13  5 46 38 30

Ambas implementaciones se comportan de forma idéntica, lo que facilita la comparación de sus costes.

Análisis de complejidad

• Complejidad espacial: El cuadrado mágico se almacena en una matriz de n por n, por lo que la complejidad espacial es O(n²).
• Complejidad del tiempo: El generador utiliza dos bucles anidados. El bucle exterior se ejecuta n veces, y el bucle interior también se ejecuta n veces, por lo que la complejidad temporal total es O(n²).

Preguntas Frecuentes