...para mis compañeros Sansanos de la Universidad Técnica Federico Santa María en los años 70

JEGC

  

 

Cuadrados Mágicos Impares de $n \times n$
Una Solución Matemática y Aplicación del Algoritmo

José Enrique González Cornejo
15 de marzo 2015




Cuadrado Mágico Impar $5\times 5$
Aplicación del Algoritmo, Haciendo 


This publication describes mathematically an algorithm that solves odd magical squares of a higher order n×n. Likewise, offers a computational interface that generates the resulting matrix online in the function of a parameter selected by the user.




 Introducción

La presente publicación es para describir matemáticamente un algoritmo que resuelve los cuadrados mágicos impares de orden mayor. Así mismo, ofrecer una interfaz computacional que genera en línea la resultante en función del parámetro seleccionado por el usuario.

El algoritmo y su aplicación computacional MagicoDocIRS, son un método genérico que permite resolver cuadrados mágicos de cualquier orden impar. En efecto, el usuario sólo ingresa un entero $n$ impar, mayor o igual que tres y el sistema procesa desplegando la matriz con la solución.

El algoritmo desarrollado por el autor José Enrique González Cornejo y aplicado en un programa computacional sobre plataforma Internet (Ver aplicación MagicoDocIRS), admite cualquier número natural impar. Sin embargo, dado que un cuadrado  de orden $141 \times 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. 

Se recomienda al 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_{n\times n} (\text{ con } n=2k+1, k \in \mathbb N)$, donde se dispone de una serie de números enteros de forma tal que la suma de los números por cada columna, de cada fila y de cada una de sus diagonales principales tenga el mismo resultado.


Figura 1

Es decir, dado un número impar de la forma $n=2k+1$, con $k \in \mathbb N$, se deben disponer los números del conjunto $A=\unicode{123}1,2,3,4, ...,n^2\unicode{125}$, para rellenar las celdas de la matriz cuadrada $M$ de orden $n \times 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 invariante $S$. (La suma de números Naturales en un Natural, de modo que $S \in \mathbb N $

Por tanto, el problema está en distribuir los números consecutivos del $1 \text{ al } n^2$, en las celdas de la matriz $M$ de orden $n \times n$, de tal manera que la suma $S$ sea la misma (i.e. $S$ es invariante), 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 $n^2$ elementos de $A$ y los ordena en una matriz cuadrada $M$ que cumple con la condición $C(x)$. (Donde $n$ es un número impar de la forma $n=2k+1$, con $k \in \mathbb N$)

$T(x) =\unicode{123} x \in A \text{ / } C(x)\unicode{125}$


Figura 2 ~ $T:A \longrightarrow B$


Nótese que la distribución de $T: A \longrightarrow M$ es una correspondencia biunívoca, o uno-a-uno y sobre. Es decir, La transformación $T$ tiene una inversa $T^{-1}$. En otras palabras, la relación es biyectiva estableciendo para cada elemento $A$ un único elemento correspondiente en $M$.

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$. Reiterando que $n$ es una entero impar mayor o igual que 3 ($n \ge 3$).

Por tanto, desde el punto de vista algebraico se debe resolver un sistema de $2(n+1)$ ecuaciones lineales.

Se observa que cada arreglo o vector es un conjunto de $n$ elementos de la forma  $m(i)=\unicode{123}a_{i1},a_{i2},a_{i3},...,a_{in}\unicode{125}$ o $m(j)=\unicode{123}a_{1j},a_{2j},a_{3j},...,a_{nj}\unicode{125}$, donde cada $a_{ij} \in \mathbb N \text {/} a_{ij} \le n^2 \text{ con } i,j=1,2,...,n$ (y donde $n$ es un número impar de la forma $n=2k+1$, con $k \in \mathbb N$)

Esto implica también que la solución de los Cuadrados Mágicos,  puede ser tratada como sub espacio vectorial sobre el cuerpo de los enteros..

Cada matriz $M$ que cumple las condiciones $C(x)$, tiene una determinante diferente de cero (i.e. no singular) y por tanto tiene una matriz inversa $M^{-1}$, tal que $M·M^{-1}=M^{-1}·M = I$, donde $I$ es la matriz Identidad del mismo orden que $M$

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).

Es decir, evitando aplicar un algoritmo computacional de resolución de carácter "carretero" o de ensayos de aproximación aleatoria o de múltiples operaciones sistemáticas para realizar el cálculo y determinar una solución.


  Base Algoritmo

La base del algoritmo que sustenta la presente solución es el Rombo Siamés, el cual se representa en una matriz cuadrada ampliada $M^*$ de orden $(2n-1) \times (2n-1)$ de números enteros , donde  se localizan los números del $1 \text{ al } n^2$ secuencialmente en forma oblicua en modulo $n$, donde $n$ es un número impar de la forma $n=2k+1$, con $k \in \mathbb N$. (Ver Figuras 5 y 6).

En el algoritmo (Ver Javascript), a las celdas vacías se les asigna el valor cero.

  • Ejemplo Cuadrado Mágico $5 \times 5$ ~ Matriz Ampliada $M^*_{9\times 9}$
  • Nota.-
  • La matriz ampliada $M^*_{9\times 9}$ para resolver el cuadrado mágico de $5 \times 5$, que se ilustra en la figura animada, se utiliza para ingresar los números,- $A=\unicode{123}1,2,3,4, ...,25\unicode{125}$ -, en forma consecutiva y oblicua, i.e. se comienza desde el centro de la primera fila de $M^*$ rellenando en diagonal desde arriba hacia abajo, partiendo desde el $1$ con los números consecutivos configurando un rombo al llegar al número $n^2$.



  • La matriz de bordes rojos inscrita en $M^*$ es la matriz $M$, que ordenaremos aplicando el método heurístico llamado Rombo Siamés, a fin de obtener la solución del cuadrado mágico impar de $n\times n$.


  • El orden $n_{A}= 2n-1$ de la matriz ampliada, en este caso es $9$, dado que el cuadrado mágico impar a resolver es de orden $n=5$.
  • La matriz buscada $M$ de orden $n \times n$, está inscrita en la matriz ampliada $M^*$.


    Figura 5

    En los cuadrados mágicos de tamaño  impar,  todas las relaciones son números enteros positivos.

    El número localizado exactamente en el centro, es fundamental para resolver el problema de la distribución.

    Es decir, el presente algoritmo se construye a partir de la base del método de construcción (Rombo Siamés) de cuadrados mágicos.

    En efecto, se desarrolla el algoritmo determinando el término general en función de $n$ del valor de esos puntos claves de $M$:

    • La suma invariante $S$.
    • El centro $c$.
    • Los vértices.
    • La aplicación de permutaciones (o swapping) de números desde $M^*$ hacia el interior de la matriz $M$
    • etc..

    El valor del número central de la ambas matrices es:



    $$\bbox[white,16px,border:1px solid black]{c=\left(\frac{n^2 + 1}{2}\right)}\qquad\quad[1]$$

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

    Por tanto, implica que la suma invariante a lograr en todas las direcciones (cada fila, cada columna y cada diagonal) es:



    $$\bbox[white,16px,border:1px solid black]{\sum_{i=1}^n m_{ij}= S=n·c}\qquad\quad[2]$$

    Las coordenadas en $M$ de este valor central $c$ son:



    $$\bbox[white,16px,border:1px solid black]{M(ka, ka), \text{ donde } ka=\frac{n +1}{2}}\qquad\quad[3]$$

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



    $$\bbox[white,16px,border:1px solid black]{ p = vsi= 1 + \frac{(n - 1)}{2}} \qquad\quad[4]$$

    El vértice superior derecho ($vsd$) de la matriz $M$ es:



    $$\bbox[white,16px,border:1px solid black]{ vsd = 1 + \frac{(n - 1)}{2}+ \frac{(n - 1)^2}{2}} \qquad\quad[5]$$


      Precisiones vía Ejemplos

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


    Figura 6

    Nótese que la serie $\unicode{123}1,2,3,4, ...,49\unicode{125}$, se configura en forma oblicua en modulo 7 en la matriz ampliada $M^*$, como lo ilustran las flechas rojas de la Figura 6.  Una vez configurada la matriz ampliada $M^*$, se aplica el algoritmo de traspaso, el cual  utiliza como  referencia  el valor central $c$ 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 6 y Figura 8).


    Figura 7

    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 6, la diagonal de pendiente positiva es la serie $\unicode{123}22,23,24,25,26,27,28\unicode{125}$, cuya suma es el invariante $S=175$. (Donde  $S=7·25$  ,  Ver expresión [2])

    Nótese que en este algoritmo, el número que ocupa el vértice superior derecho vsd de la matriz $M$,  es equivalente a:



    $$\bbox[white,16px,border:1px solid black]{vsd = p + (p-1)·(n-1)}$$

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



    $$\bbox[white,16px,border:1px solid black]{vsd = 1 + \frac{(n-1)}{2} + \frac{(n-1)^2}{2}} $$

    La sucesión de valores que va adquiriendo el $vsd$, en función de $n$ se ilustra a continuación:



    $n$ $vsd$ $Secuencia$
    3 4 1+1+2=4
    5 11 1+2+8=11
    7 22 1+3+18=22
    9 37 1+4+32=37
    11 56 1+5+50=56
    13 79 1+6+72=79
    ... ... ...
    n $$1+\frac{(n-1)}{2}+\frac{(n-1)^2}{2}$$ ...

    Nótese que estos vértices derechos de los cuadrados $M$ son el valor inicial de la serie secuencial que se ingresa en la segunda diagonal del cuadrado y su suma es la invariante $S$:

    $n$ $vsd$ $\text{2da Diagonal}$ $\sum$
    3 4 {4,5,6} 15
    5 11 {11,12,13,14,15} 65
    7 22 {22,23,24,25,26,17,28} 175
    9 37 {37,38,39,40,41,42,43,44,45} 369
    ... ... ... ...
    n $$1+\frac{(n-1)}{2}+\frac{(n-1)^2}{2}$$ {vsd,vsd+1,vsd+2,...,vsd+(n-1)} $$n·c$$

    En el ejemplo  de orden $7x7$, se tiene que  $vsd=22$ y su segunda diagonal es {22,23,24,25,26,17,28}, cuya suma es 175.

    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 con respecto a los ejes centrales..


    Figura 8
     

    En efecto, el ejemplo de la Figura 8, muestra las permutaciones en la columna central, desde los valores externos de $M^*_{13 \times 13}$ hacia las celdas de $M_{7 \times 7}$ con valores ceros. 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 permuta con 49] y [9 permuta con 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)\longrightarrow M(5,4)$$ El valor $M^*(1,7)=1$ se permuta con $M(5,4)=0$
    $$M^*(13,7)\longrightarrow M(3,4)$$ El valor $M^*(13,7)=49$ se permuta con $M(3,4)=0$
    $$M^*\longrightarrow M(7,4)$$ El valor $M^*(3,7)=9$ se permuta con $M(7,4)=0$
    $$M^*(11,7)\longrightarrow M(1,4)$$ El valor $M^*(11,7)=41$ se permuta con $M(1,4)=0$

    Resultante Algoritmo: Matriz de orden $7 x 7$


    Figura 9


     Función Javascript: 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
         }
       }
     }
    }
    }

     Otra solución $7 x 7$: Cuadrado Mágico de la Ermita "Virgen del Calvario"


    Cuadrado Mágico 7x7 en Zurgena, Almería. Ermita Virgen del Calvario


    Se  trata de una de las soluciones, porque existen otros algoritmos con otras distribuciones que cumplen con las condiciones de un cuadrado mágico impar. Por ejemplo, en el caso de $7 x 7$, está el cuadrado mágico de la Ermita "Virgen del Calvario" (ver figura 10),  la cual presenta otra distribución de los números {1,2,3,...,49} diferentes a la matriz de la figura 9 generada por la transformacion $T$. Estas soluciones sólo coinciden en el número central $c=25$

    En efecto, cuadrado mágico de la Ermita “Virgen del Calvario” en Almería, que es la siguiente matriz solución:


    Figura 10

     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 del vértice superior izquierdo $p=2$  (Ver [4]) y el valor central c=5 (Ver [1]).
     

    3.- Se aplica permutación externa vertical con 1 y 9

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

     

    4.- Se aplica Permutación externa horizontal hacia en interior de las celdas vacías (o $0$) de 3 y 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.

    La solución algebraica también puede simplificarse con algunas de las propiedades que se pueden extraer a primera vista del Rombo Siamés. En efecto, este ordenamiento ofrece una serie de relaciones numéricas que se deducen en forma directa, las cuales reducen en forma significativa el sistema de ecuaciones lineales sobre $\mathbb Z$ que es necesario estructurar cuando se plantea el problema bajo este enfoque.

    Por ejemplo:

     


    Figura 3

    i)  La diagonal principal de la matriz $M$  que parte del vértice superior izquierdo  hacia el vértice inferior derecho  (i.e la diagonal de pendiente positiva), es un vector o arreglo de $n$ términos que responden a una progresión aritmética, cuya  diferencia es $n$ (i.e. la diferencia constante es la misma que el orden del cuadrado) y que suman $S$ que es la traza de magnitud invariante de $M$. El valor $p$ de este vértice vsi es $p = 1 + \frac(n - 1){2}$, 

    Reiterando que $n$ es una entero impar mayor o igual que 3.(Ver expresión [4]). Es decir, el arreglo de la forma $\unicode{123}p, p+n, p+2n,....,p + n(n - 1)\unicode{125}$ constituye la diagonal principal de $M$

    ii) La diagonal de la matriz $M$  que parte del vértice superior derecho hacia el vértice inferior izquierdo (i.e la diagonal de pendiente negativa), es un arreglo de números consecutivos que suman $S$. El valor de este vértice superior derecho es $vsd = p + (p-1)·(n-1)$ (Ver expresión [5])

    iii) La intersección de las diagonales es el número central de la matriz. Es decir, queda localizado en el centro del cuadrado de orden impar. Este número central $c$ es clave para la solución del problema.(Ver expresión [1]))

    Con la propiedades concluidas del Rombo Siamés se reduce el sistema de ecuaciones considerablemente a la siguiente operación matricial:

    Donde los valores de la matriz marcados con un circulo rojo y el valor invariante $S$ del vector resultante, están previamente determinados. Además, el Rombo Siamés señala claramente las permutaciones a realizar desde una matriz ampliada, donde se inscribe $M$.


     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.

    (Ver Aspectos Históricos~Pedro Alegría ~ Septiembre 2009 • 2009 ko Iraila)

    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 mágicas, 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 + \frac(n - 1){2}$ 9
    Vértice Superior Derecho $vsd=1 + \frac{(n-1)}{2} + \frac{(n-1)^2}{2}$ $137$
    Coordenadas Centrales $(m,m)$ $(9,9)$
    Valor Central $c = M(m,m) = \frac{n^2+1}{2} $145$
    Suma (Filas, Columnas, Diagonales), $S = n·c = 17·45$ $2465$


     


    Canal de Videos

     

    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
    ¿Cómo Entender el Teorema de Bayes en forma Simple?
    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
    Diseño y Construción Gráfica de Logo DocIRS Grafo con Funciones Análiticas

     

     



    DocIRS © 1988-