logo de DocIRS

Descripción Matemática y Aplicación del Algoritmo 
Cuadrados Mágicos Impares
José Enrique González Cornejo
15 de marzo 2015

...para mis compañeros Sansanos de la Universidad en los años 70

JEGC


Introducción

La presente publicación es para ofrecer una interfaz que contiene el algoritmo para cuadrados mágicos de orden mayor.

El algoritmo y a su aplicación computacional MagicoDocIRS, son un método genérico que permite resolver cuadrados mágicos de cualquier orden impar.

El algoritmo desarrollado por el autor y aplicado en un programa computacional sobre plataforma Internet (Ver aplicación MagicoDocIRS), admite cualquier numero natural impar. Sin embargo, dado que un cuadrado  de orden 141 x 141 significa configurar y publicar en una vista  Web de una matriz de 19.881  celdas, se ha limitado la aplicación, - mediante un listbox para seleccionar el orden-, hasta esa cifra máximo. 

La aplicación MagicoDocIRS admite exportar a una planilla Excel la matriz resultante, a fin de que lector pueda comprobar,  visualizar e investigar las relaciones numéricas que conforman el cuadrado mágico generado.

 


Interfaz de la Aplicación MagicoDocIRS

Definición y Enunciado

Un cuadrado mágico impar es una matriz cuadrada M, donde se dispone de una serie de números enteros de forma tal que la suma de los números por cada columna, por cada fila y por cada una de sus diagonales principales tenga el mismo resultado.


Figura 1

Es decir, dado un numero impar de la forma n=2*k+1, con kN,  se deben disponer los números del conjunto A= {1,2,3,4, ...,n2}, para rellenar las celdas de la matriz cuadrada M de orden n x n, con la condición C(x), la cual requiere que la sumatoria de filas, columnas y  las dos diagonales principales de M sumen la  misma constante S. (La suma de números Naturales en un Natural, de modo que SN)

Por tanto, el problema está en distribuir los números  del 1 al , en las celdas de la matriz M de orden n x n, de tal manera que la suma S sea la misma, en todos los sentidos señalados en la Figura 1.
 

Algoritmo: Transformación T(x)

El algoritmo MagicoDocIRS es una Transformación T que toma los n2 elementos de A y los ordena en una matriz cuadrada M que cumple con la condición C(x).

T(x)={ x A / C(x) }

Figura 2

La matriz M bajo las condiciones C(x) a resolver, está compuesta por n arreglos horizontales (filas), n arreglos verticales (columnas)  y 2 arreglos diagonales. Es decir, 2(n+1) arreglos, donde con cada uno de ellos se constituye una ecuación cuya suma es S.

Por tanto, desde el punto de vista algebraico se debe resolver un sistema de 2(n+1) ecuaciones lineales. Nótese que cada arreglo es un conjunto de n elementos de la forma  m(i)={ai1,ai2,ai3,...,ain} o m(j)={a1j,a2j,a3j,...,anj}, donde cada aijN / aij<=n2, con i,j=1,2,...n. Esto implica también que la solución de los Cuadrados Mágicos,  puede ser tratada como subespacio vectorial.

Afortunadamente, a lo largo de la historia, se han descubierto diferentes métodos de resolución sintética, -  en este caso el Rombo Siamés-, que ayudan a simplificar y resolver el cuadrado mágico por construcción, sin tener que despejar tantas incógnitas. (Ver analogía con el Triangulo de Pascal).


Orígenes Históricos

Los cuadrados mágicos se estudian desde hace 3 milenios antes de Cristo en China. Posteriormente en  otras regiones de Asia, India, Egipto y Grecia. En Europa  fue publicado en Francia en 1691 por Simón de la Loubere, llamado a veces Método Siamés, dado que él lo aprendió en esas tierras. (Ver Cuadrados Mágicos Wikipedia)

Existen decenas de evidencias que estas estructuras numéricas de orden menor ya se conocían a  lo largo de la historia y muchos fueron los que intentaron resolver este rompecabezas matemático. Fue en el Renacimiento cuando se resolvió, - en forma heurística-,  el problema de orden mayor,  por diversos matemáticos (Stifel, Fermat, Pascal, Leibnitz, Frénicle, Bachet, La Hire, Saurin, Euler,...), pero siempre inspirados y copiando  las construcciones antiguas del cuadrado mágico  proveniente del oriente.
 

Base Algoritmo

La base del algoritmo que sustenta la presente solución es el rombo, el cual se representa en una matriz cuadrada ampliada M* de orden (2*n+1) x (2*n+1) de números enteros , donde  se localizan los números del 1 al secuencialmente en forma oblicua en modulo n (Ver Figuras 4 y 5).   A las celdas vacías se les asigna el valor cero.

La matriz buscada M de orden n x n, está inscrita en la matriz ampliada M*.


Figura 3

En los cuadrados mágicos de tamaño  impar,  todas las relaciones son números enteros positivos. El numero localizado exactamente en el centro, es fundamental para resolver el problema de la distribución. El valor del numero central de la ambas matrices es:

c = (n²/2+0.5)  [1]

Este valor c, es directamente deducible de la serie {1,2,3,4, ...,n2}, tomando el primer término sumado al último, dividido por 2. (Ver Sumatoria de Gauss)

Por tanto, implica que la suma constante a lograr en todas las direcciones es

S = n·c  [2]

Las coordenadas en M de este valor central c son:

m(ka, ka), donde ka = n/2+0.5 [3]

 

El vértice superior izquierdo (vsi) de la matriz M es:

p = 1 + (n - 1) / 2 [4]

y las coordenadas de p en M*, coinciden m*(p,p)=p.

 

Precisiones vía Ejemplos

La siguiente ilustración muestra un paso intermedio para la resolución de una matriz M de orden 7 x 7, inscrita en en la matriz ampliada M* de orden 13 x 13, cuyo valor central c=25, localizado en en m(4,4) y el vértice superior izquierdo es p=4

Figura 4
 

Nótese que los la serie {1,2,3,4, ...,49}, se configura en forma oblicua en modulo 7 en la matriz ampliada M*, como lo ilustran las flechas rojas de la Figura 4.  Una vez configurada la matriz ampliada M*, se aplica el algoritmo de traspaso, el cual  utiliza como  referencia  el valor central y  el  vértice superior izquierdo p, como así mismo las propiedades simétricas de la matriz.

Es decir,  ahí se aplica una rutina que permuta los números diferentes de cero M*, - externos a M-, hacia el interior, teniendo como referencia el vértice superior izquierdo p  y el valor central c. El algoritmo cuenta con dos funciones: una que opera verticalmente en los "swaping" y la otra horizontalmente, (Ver figura 4 y Figura 6)


Figura 5

Nótese que en esta construcción, MagicoDocIRS siempre contempla que la diagonal de pendiente positiva de la matriz M, es una serie consecutiva. Es decir, los números del vértice superior derecho  hasta el vértice inferior izquierdo, son n números consecutivos.  En el ejemplo de la Figura 4, la diagonal de pendiente positiva es la serie {22,23,24,25,26,27,28}, cuya suma S=175. (Donde  S=7·25  ,  ver formula [2])

Nótese que en este algoritmo, el numero que ocupa el vértice superior derecho vsd de la matriz M,  es:

 vsd = p + (p-1)·(n-1) [5]

Es decir, que si se sustituye el valor de de  [4], en la expresión [5], se obtiene:

vsd = 1 + (n-1)/2 + (n-1)2/2 [6]

En el ejemplo  de orden 7x7, se tiene que  vsd=22.

Dejamos al lector la tarea de continuar encontrando las decenas de relaciones y series (más bien progresiones) que se generan  en función de n, dentro el cuadrado mágico. (Ejecutar la aplicación MagicoDocIRS para visualizar cuadrados de tamaños diferentes).

Ejemplo (Resolver la Matriz de orden 7 x 7)

Se puede observar como se distribuyen los valores simétricamente alrededor del eje horizontal. Los valores de las casillas de ambos lados ,  se posicionan  al interior de M aplicando la propiedad de simetría.


Figura 6

En efecto, el ejemplo de la Figura 6, muestra las permutaciones en la columna central, desde los valores externos a M hacia las celdas con valores ceros de M. Los pares, -de este ejemplo-, que van ingresando desde M* exterior,  y posicionándose en el interior de la columna central de M, son (1,49) y (9,41), la primera coordenada del par ordenado es la externa superior a M y la segunda coordenada es la externa inferior.

Nótese que los valores superiores se desplazan hacia abajo del eje central horizontal y los valores inferiores hacia arriba del eje central de M.

Téngase en cuenta que las coordenadas de M* y M se referencian matricialmente en forma independiente.

M*(1,7)------>M(5,4)  El valor M*(1,7)=1 se permuta con M(5,4)=0
M*(13,7)------>M(3,4) El valor M*(13,7)=49 se permuta con M(3,4)=0
M*(3,7)------>M(7,4) El valor M*(3,7)=9 se permuta con M(7,4)=0
M*(11,7)------>M(1,4 El valor M*(11,7)=41 se permuta con M(1,4)=0

Finalmente, la solución del ejemplo de cuadrado mágico 7 x 7 es la siguiente:

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

Figura 7

Ilustración  Función Permuta Valores Verticales

Este proceso se repite para todas las filas menores que p y análogamente para los valores externos de la columnas menores que p.

function Permuta_Valores_Verticales(columna){
/*Autor: José Enrique González Cornejo.
Desarrollo en DOM javascript y ASP.
Aplicación del algoritmo
MagicoDocIRS

Rutina que permuta valores externos de M*
verticalmente hacia la matriz M
Ejecutar
MagicoDocIRS
*/

 var par=new Array()
 var kpar=0
  for (var i=1;i<=p-1;i++)
  {
   var iden1="td_" + i + "_" + columna
   var iden2="td_" + (ampliado-i+1) + "_" + columna

   arriba=document.getElementById(iden1).innerHTML
   abajo=document.getElementById(iden2).innerHTML

   if (arriba!=0 && abajo!=0)
    {
    kpar=kpar+1
    par[kpar]=document.getElementById(iden1).innerHTML + "," + document.getElementById(iden2).innerHTML
    document.getElementById(iden1).innerHTML="0"
    document.getElementById(iden2).innerHTML="0"
    }
  }

pk=0
for (var i=p;i<=p + (n-1);i++)
{
var idenp="td_" + i + "_" + columna
temp=document.getElementById(idenp).innerHTML
 if (temp==0)
  {
   var posicion1=idenp
   var posicion2="td_" + (ampliado-(i-1)) + "_" + columna
   arriba=document.getElementById(posicion1).innerHTML
   abajo=document.getElementById(posicion2).innerHTML
   if (abajo==0 && arriba==0)
   {
     if(pk<kpar)
     {
      var auxiliar1=par[kpar-pk]
      cadena1=auxiliar1.split(",")
      document.getElementById(posicion1).innerHTML=cadena1[1]
      document.getElementById(posicion2).innerHTML=cadena1[0]
      pk=pk+1
     }
   }
 }
}
}

 

Ejemplo Paso a Paso con n=3

1.- Se configura Matriz Ampliada M* de 5 x 5, localizando los números del 1 al 9 en forma oblicua en modulo 3.
2.- Se distingue la matriz M de orden 3 x 3, - marcada de amarillo-, inscrita en M*. Cuyas referencias para el algoritmo son el valor p=2  (Ver [4]) y el valor central c=5 (Ver [1]).
 

3.- Se aplica permutación externa vertical con el par (1,9)

Nota: El numero de pares a permutar va aumentando según el orden de la matriz.

 

4.- Se aplica Permutación externa horizontal con el par (3,7)
5.- Terminada las Permutaciones de M* hacia M y vaciado el rombo
6.- Se despeja la la Matriz M Resultante (cuya sumas S=15 (Ver [2]), en filas, columnas, diagonales)

Síntesis

Los cuadrados mágicos,  no tienen aplicación técnica conocida, pero cualquier matemático siempre quiere resolver y curiosear. El modelo aquí presentado no utiliza ningún recurso aleatorio.

Para finalizar, ilustramos a continuación un cuadro resuelto de orden 17 x 17, realizado por la aplicación MagicoDocIRS e  Invitamos a los lectores a continuar encontrando la múltiples relaciones en función de n, que se presentan en estas estructuras numéricas, mediante el programa MagicoDocIRS.

Ejemplo Resuelto (Matriz de orden 17 x 17)

Datos Básicos del Cuadro
Orden de la Matriz M 17 x 17
Secuencia 1,2,...,289
Vértice Superior Izquierdo p = 1 + (n - 1) / 2 9
Vértice Superior Derecho vsd=1 + (n-1)/2 + (n-1)2/2 137
Coordenadas Centrales (m,m) (9,9)
Valor Central M(m,m)=n2/2+0.5 145
Suma (Filas, Columnas, Diagonales) 2465

9 170 25 186 41 202 57 218 73 234 89 250 105 266 121 282 137
154 26 187 42 203 58 219 74 235 90 251 106 267 122 283 138 10
27 171 43 204 59 220 75 236 91 252 107 268 123 284 139 11 155
172 44 188 60 221 76 237 92 253 108 269 124 285 140 12 156 28
45 189 61 205 77 238 93 254 109 270 125 286 141 13 157 29 173
190 62 206 78 222 94 255 110 271 126 287 142 14 158 30 174 46
63 207 79 223 95 239 111 272 127 288 143 15 159 31 175 47 191
208 80 224 96 240 112 256 128 289 144 16 160 32 176 48 192 64
81 225 97 241 113 257 129 273 145 17 161 33 177 49 193 65 209
226 98 242 114 258 130 274 146 1 162 34 178 50 194 66 210 82
99 243 115 259 131 275 147 2 163 18 179 51 195 67 211 83 227
244 116 260 132 276 148 3 164 19 180 35 196 68 212 84 228 100
117 261 133 277 149 4 165 20 181 36 197 52 213 85 229 101 245
262 134 278 150 5 166 21 182 37 198 53 214 69 230 102 246 118
135 279 151 6 167 22 183 38 199 54 215 70 231 86 247 119 263
280 152 7 168 23 184 39 200 55 216 71 232 87 248 103 264 136
153 8 169 24 185 40 201 56 217 72 233 88 249 104 265 120 281


Figura 7


Artículos Relacionados
MagicoDocIRS (Aplicación asociada al presente artículo)
Logo DocIRS : Grafo conexo definido como árbol
El Problema de la Ruta Óptima
Simulación Aleatoria de Algoritmo Por Tramos DocIRS para la Ruta Optima
Simulación Aleatoria de Algoritmo Por Permutaciones DocIRS para la Ruta Optima
Ejemplo Simple Permutaciones para la Ruta Optima
Logit: Función de distribución dicotómica para el Scoring
Geometrías Cualitativas
El Profesor Josegonzky resuelve ganar al hipnotizador
Modelo de estimación del factor Fc ~ Acerca de variables de entorno
Modelo Insumo-Producto, Costeo y Arquitectura de Negocios
Algoritmo Indicadores PMO
Fundamentos de los Lenguajes Estructurados.
Estimación de Precios de los Servicios-Productos DocIRS, Bajo el Modelo SAAS 
Complemento de Conceptos Matemáticos ~ Mínimos Cuadrados
Complemento de Conceptos Matemáticos ~ Regresión Múltiple
Complemento de Conceptos Matemáticos ~ Distancia de un Punto a una Recta
Descripción Algoritmo de Distribución Aleatoria de Suma 1
Algoritmo en Acción ~ Herramienta de Distribución Aleatoria de Suma 1