Cuadrado Mágico – Resuelve rompecabezas de 3×3 usando C & Python Ejemplos
sarah chen
¿Qué es el Cuadrado Mágico?
Un cuadrado mágico es una matriz cuadrada con una disposición especial de números. Estos números están dispuestos de manera que la suma de los números en cada diagonal, fila y columna permanezca igual. Los juegos de cuadrados mágicos son acertijos de lógica simples que se utilizan en matemáticas recreativas.
Ejemplo de cuadrados mágicos:
El diagrama anterior es un ejemplo de un cuadrado mágico de orden 3. La suma de cada diagonal, fila y columna es 15.
Cómo funciona el Cuadrado Mágico
Los cuadrados mágicos son matrices n*n que constan de n^2 números enteros positivos. El número de filas o columnas de una matriz cuadrada se denomina orden de la matriz.
Por lo general, los rompecabezas de cuadrados mágicos tienen órdenes impares y contienen los números enteros de 1 a n^2. La suma de cada diagonal, fila y columna es la misma. Este número se llama suma mágica o constante mágica. Por lo general, esta suma mágica depende del orden de la matriz. La fórmula de los cuadrados mágicos para la suma mágica de orden n es:
Tomemos un ejemplo de un cuadrado mágico con números enteros 3. Entonces, la suma mágica sería:
¿Por qué se llaman Magia?
Los matemáticos antiguos se sentían fascinados por la naturaleza de varias combinaciones interesantes de números. El cuadrado mágico era una de ellas. La evidencia más antigua de cuadrados mágicos se remonta a China en el año 190 a. C.
Algunos estudios muestran evidencias de la existencia del rompecabezas de los cuadrados mágicos en el antiguo Japón, la India y Arabia. Según algunas leyendas, se suponía que esas formaciones especiales de números estaban relacionadas con el mundo mágico. Por eso, esos cuadrados recibieron el nombre de cuadrados mágicos.
Tipos de cuadrado mágico
Existen diferentes variantes de la matemática de los cuadrados mágicos:
- Cuadrado Mágico Normal: Este tipo de cuadrado mágico contiene los primeros n^2 números.
- Cuadrado Semi-Mágico: En este tipo, sólo las filas y la columna suman la constante mágica.
- Cuadrado Mágico Sencillo: A diferencia del tipo anterior, las filas, columnas y ambas diagonales suman la constante mágica.
- El cuadrado mágico más perfecto: Este es un cuadrado mágico normal con dos propiedades especiales. Aquí, cada subcuadrado de 2 por 2 de la matriz suma un total de 2(n^2+1). Y cualquier par de números que estén separados por n/2 cuadrados de la cuadrícula suma n^2+1.
Según sus propiedades, existen muchos más tipos de cuadrados mágicos, pero siempre que mencionamos el cuadrado mágico, asumimos que se trata de un cuadrado mágico normal y simple de orden impar.
Algoritmo para generar cuadrado mágico
El algoritmo para generar cuadrados mágicos de orden impar es:
- El primer número o 1 se almacenará en (n/2, n-1), donde la primera coordenada es la posición de la fila y la segunda, la posición de la columna. Para los pasos posteriores, denotaremos esta posición como (x, y).
- Los siguientes números se almacenarán en (x-1, y+1). Si la posición no es válida, tendremos en cuenta las siguientes condiciones.
- Si la posición de la fila es -1, se deformará a n-1. De manera similar, si la posición de la columna calculada es n, se deformará a 0.
- La posición de la fila se incrementará en 1 y la posición de la columna se reducirá en 2 si la posición calculada ya contiene un número.
- Si la posición de la fila es -1 y la posición de la columna correspondiente es n, la nueva posición será (0, n-2.
Nota: Este algoritmo solo genera cuadrados mágicos válidos de orden impar. También consideramos este cuadrado mágico como un cuadrado mágico normal con los primeros n^2 números. Además, puede haber múltiples soluciones para el mismo valor de n.
Tomemos un ejemplo y veamos cómo funciona. Digamos que queremos encontrar el cuadrado mágico de orden 3. Como será un cuadrado mágico simple y normal de orden impar, contendrá todos los números del 1 al 3^2 o 9.
¿Cómo funciona?
De acuerdo con nuestro algoritmo, los pasos serán los siguientes:
Paso 1) El primer número o 1 estará en la posición (3/2, 3-1) o (1, 2). Por convención, considera x = 1 e y = 2 para los pasos posteriores.
Paso 2) La posición del resto de números se calculará de la siguiente manera:
Posición del número 2:
El siguiente número estará en (x-1, y+1) o (0, 3), que no es una posición válida. Al usar la condición (a), la posición válida correspondiente sería (0,0). Entonces, x= 0, y= 0.
Posición del número 3:
El número 3 estará en (x-1, y+1) o (-1, 1), que no es una posición válida. Al usar la condición (a), la posición de fila válida sería n-1 o 2. Entonces, el número 3 estará en (2, 1). Para el siguiente número, x= 2, y= 1.
Posición del número 4:
El número 4 debe estar en (x-1, y+1) o (1, 2), que es una posición válida. Pero esa posición ya contiene un número. Según la condición (b), la posición válida sería (1+1, 2-2) o (2,0). Para el siguiente número 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 válida. Para el siguiente número 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 válida. Para el siguiente número x= 0, y= 2.
Posición del número 7:
El número 7 debe estar en (x-1, y+1) o (-1, 3), que no es una posición válida. Según la condición (c), la posición válida sería (0, n-2) o (0, 1). Para el siguiente número x= 0, y= 1.
Posición del número 8:
El número 8 debe estar en (x-1, y+1) o (-1, 2), que no es una posición válida. Al usar la condición (a), la posición válida sería (2, 2). Para el siguiente número x= 2, y= 2.
Posición del número 9:
El número 9 debe estar en (x-1, y+1) o (1, 3), que no es una posición válida. Al usar la condición (a), la posición válida sería (1, 0).
Pseudocódigo
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
C++ Código 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
Python Código 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
Análisis de complejidad
- Complejidad espacial: Para mantener la matriz del cuadrado mágico, necesitamos una matriz *n. Por lo tanto, la complejidad espacial sería O(n^2).
- Complejidad del tiempo: El código que usamos para generar la matemática de los cuadrados mágicos consta de dos bucles. El bucle externo se ejecuta n veces y el bucle interno también se ejecuta n veces. En definitiva, la complejidad temporal es O(n^2).
