Cuadrado Mágico | orden impar

Un cuadrado mágico de orden n es una disposición de n 2 números, generalmente enteros distintos, en un cuadrado, de modo que los n números en todas las filas, todas las columnas y ambas diagonales suman la misma constante. Un cuadrado mágico contiene los números enteros del 1 al n 2
La suma constante en cada fila, columna y diagonal se denomina constante mágica o suma mágica , M. La constante mágica de un cuadrado mágico normal depende únicamente de n y tiene el siguiente valor: 
M = n(n 2 +1)/2

For normal magic squares of order n = 3, 4, 5, ...,
the magic constants are: 15, 34, 65, 111, 175, 260, ... 

En esta publicación, discutiremos cómo podemos generar programáticamente un cuadrado mágico de tamaño n. Este enfoque solo tiene en cuenta los valores impares de n y no funciona para números pares. Antes de continuar, considere los siguientes ejemplos:

Magic Square of size 3
-----------------------
  2   7   6
  9   5   1
  4   3   8
Sum in each row & each column = 3*(32+1)/2 = 15


Magic Square of size 5
----------------------
  9   3  22  16  15
  2  21  20  14   8
 25  19  13   7   1
 18  12   6   5  24
 11  10   4  23  17
Sum in each row & each column = 5*(52+1)/2 = 65


Magic Square of size 7
----------------------
 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
Sum in each row & each column = 7*(72+1)/2 = 175

¿Encontraste algún patrón en el que se almacenan los números? 

En cualquier cuadrado mágico, el primer número, es decir, 1, se almacena en la posición (n/2, n-1). Sea esta posición (i,j). El siguiente número se almacena en la posición (i-1, j+1) donde podemos considerar cada fila y columna como una array circular, es decir, se envuelven.

Se cumplen tres condiciones:

  1. La posición del siguiente número se calcula disminuyendo el número de fila del número anterior en 1 e incrementando el número de columna del número anterior en 1. En cualquier momento, si la posición de fila calculada se convierte en -1, volverá a n- 1. De manera similar, si la posición de la columna calculada se convierte en n, volverá a 0.
  2. Si el cuadrado mágico ya contiene un número en la posición calculada, la posición de la columna calculada se reducirá en 2 y la posición de la fila calculada se incrementará en 1.
  3. Si la posición de la fila calculada es -1 y la posición de la columna calculada es n, la nueva posición sería: (0, n-2). 
Example:
Magic Square of size 3
----------------------
 2  7  6
 9  5  1
 4  3  8 

Steps:
1. position of number 1 = (3/2, 3-1) = (1, 2)
2. position of number 2 = (1-1, 2+1) = (0, 0)
3. position of number 3 = (0-1, 0+1) = (3-1, 1) = (2, 1)
4. position of number 4 = (2-1, 1+1) = (1, 2)
   Since, at this position, 1 is there. So, apply condition 2.
   new position=(1+1,2-2)=(2,0)
5. position of number 5=(2-1,0+1)=(1,1)
6. position of number 6=(1-1,1+1)=(0,2)
7. position of number 7 = (0-1, 2+1) = (-1,3) // this is tricky, see condition 3 
   new position = (0, 3-2) = (0,1)
8. position of number 8=(0-1,1+1)=(-1,2)=(2,2) //wrap around
9. position of number 9=(2-1,2+1)=(1,3)=(1,0) //wrap around

Basado en el enfoque anterior, el siguiente es el código de trabajo: 

C++

// C++ program to generate odd sized magic squares
#include <bits/stdc++.h>
using namespace std;
 
// A function to generate odd sized magic squares
void generateSquare(int n)
{
    int magicSquare[n][n];
 
    // set all slots as 0
    memset(magicSquare, 0, sizeof(magicSquare));
 
    // Initialize position for 1
    int i = n / 2;
    int j = n - 1;
 
    // One by one put all values in magic square
    for (int num = 1; num <= n * n;) {
        if (i == -1 && j == n) // 3rd condition
        {
            j = n - 2;
            i = 0;
        }
        else {
            // 1st condition helper if next number
            // goes to out of square's right side
            if (j == n)
                j = 0;
 
            // 1st condition helper if next number
            // is goes to out of square's upper side
            if (i < 0)
                i = n - 1;
        }
        if (magicSquare[i][j]) // 2nd condition
        {
            j -= 2;
            i++;
            continue;
        }
        else
            magicSquare[i][j] = num++; // set number
 
        j++;
        i--; // 1st condition
    }
 
    // Print magic square
    cout << "The Magic Square for n=" << n
         << ":\nSum of "
            "each row or column "
         << n * (n * n + 1) / 2 << ":\n\n";
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
 
            // setw(7) is used so that the matrix gets
            // printed in a proper square fashion.
            cout << setw(4) << magicSquare[i][j] << " ";
        cout << endl;
    }
}
 
// Driver code
int main()
{
 
    // Works only when n is odd
    int n = 7;
    generateSquare(n);
    return 0;
}
 
// This code is contributed by rathbhupendra

C

// C program to generate odd sized magic squares
#include <stdio.h>
#include <string.h>
 
// A function to generate odd sized magic squares
void generateSquare(int n)
{
    int magicSquare[n][n];
 
    // set all slots as 0
    memset(magicSquare, 0, sizeof(magicSquare));
 
    // Initialize position for 1
    int i = n / 2;
    int j = n - 1;
 
    // One by one put all values in magic square
    for (int num = 1; num <= n * n;) {
        if (i == -1 && j == n) // 3rd condition
        {
            j = n - 2;
            i = 0;
        }
        else {
            // 1st condition helper if next number
            // goes to out of square's right side
            if (j == n)
                j = 0;
 
            // 1st condition helper if next number
            // is goes to out of square's upper side
            if (i < 0)
                i = n - 1;
        }
        if (magicSquare[i][j]) // 2nd condition
        {
            j -= 2;
            i++;
            continue;
        }
        else
            magicSquare[i][j] = num++; // set number
 
        j++;
        i--; // 1st condition
    }
 
    // Print magic square
    printf("The Magic Square for n=%d:\nSum of "
           "each row or column %d:\n\n",
           n, n * (n * n + 1) / 2);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("%3d ", magicSquare[i][j]);
        printf("\n");
    }
}
 
// Driver program to test above function
int main()
{
    int n = 7; // Works only when n is odd
    generateSquare(n);
    return 0;
}

Java

// Java program to generate odd sized magic squares
import java.io.*;
 
class GFG {
    // Function to generate odd sized magic squares
    static void generateSquare(int n)
    {
        int[][] magicSquare = new int[n][n];
 
        // Initialize position for 1
        int i = n / 2;
        int j = n - 1;
 
        // One by one put all values in magic square
        for (int num = 1; num <= n * n;) {
            if (i == -1 && j == n) // 3rd condition
            {
                j = n - 2;
                i = 0;
            }
            else {
                // 1st condition helper if next number
                // goes to out of square's right side
                if (j == n)
                    j = 0;
 
                // 1st condition helper if next number is
                // goes to out of square's upper side
                if (i < 0)
                    i = n - 1;
            }
 
            // 2nd condition
            if (magicSquare[i][j] != 0) {
                j -= 2;
                i++;
                continue;
            }
            else
                // set number
                magicSquare[i][j] = num++;
 
            // 1st condition
            j++;
            i--;
        }
 
        // print magic square
        System.out.println("The Magic Square for " + n
                           + ":");
        System.out.println("Sum of each row or column "
                           + n * (n * n + 1) / 2 + ":");
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++)
                System.out.print(magicSquare[i][j] + " ");
            System.out.println();
        }
    }
 
    // driver program
    public static void main(String[] args)
    {
        // Works only when n is odd
        int n = 7;
        generateSquare(n);
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python program to generate
# odd sized magic squares
# A function to generate odd
# sized magic squares
 
 
def generateSquare(n):
 
    # 2-D array with all
    # slots set to 0
    magicSquare = [[0 for x in range(n)]
                   for y in range(n)]
 
    # initialize position of 1
    i = n // 2
    j = n - 1
 
    # Fill the magic square
    # by placing values
    num = 1
    while num <= (n * n):
        if i == -1 and j == n:  # 3rd condition
            j = n - 2
            i = 0
        else:
 
            # next number goes out of
            # right side of square
            if j == n:
                j = 0
 
            # next number goes
            # out of upper side
            if i < 0:
                i = n - 1
 
        if magicSquare[int(i)][int(j)]:  # 2nd condition
            j = j - 2
            i = i + 1
            continue
        else:
            magicSquare[int(i)][int(j)] = num
            num = num + 1
 
        j = j + 1
        i = i - 1  # 1st condition
 
    # Printing magic square
    print("Magic Square for n =", n)
    print("Sum of each row or column",
          n * (n * n + 1) // 2, "\n")
 
    for i in range(0, n):
        for j in range(0, n):
            print('%2d ' % (magicSquare[i][j]),
                  end='')
 
            # To display output
            # in matrix form
            if j == n - 1:
                print()
 
# Driver Code
 
 
# Works only when n is odd
n = 7
generateSquare(n)
 
# This code is contributed
# by Harshit Agrawal

C#

// C# program to generate odd sized magic squares
using System;
 
class GFG {
 
    // Function to generate odd sized magic squares
    static void generateSquare(int n)
    {
        int[, ] magicSquare = new int[n, n];
 
        // Initialize position for 1
        int i = n / 2;
        int j = n - 1;
 
        // One by one put all values in magic square
        for (int num = 1; num <= n * n;) {
            if (i == -1 && j == n) // 3rd condition
            {
                j = n - 2;
                i = 0;
            }
            else {
                // 1st condition helper if next number
                // goes to out of square's right side
                if (j == n)
                    j = 0;
 
                // 1st condition helper if next number is
                // goes to out of square's upper side
                if (i < 0)
                    i = n - 1;
            }
 
            // 2nd condition
            if (magicSquare[i, j] != 0) {
                j -= 2;
                i++;
                continue;
            }
            else
                // set number
                magicSquare[i, j] = num++;
 
            // 1st condition
            j++;
            i--;
        }
 
        // print magic square
        Console.WriteLine("The Magic Square for " + n
                          + ":");
        Console.WriteLine("Sum of each row or column "
                          + n * (n * n + 1) / 2 + ":");
 
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++)
                Console.Write(magicSquare[i, j] + " ");
            Console.WriteLine();
        }
    }
 
    // driver program
    public static void Main()
    {
 
        // Works only when n is odd
        int n = 7;
 
        generateSquare(n);
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// php program to generate odd sized
// magic squares
 
// A function to generate odd sized
// magic squares
function generateSquare($n)
{
 
    // set all slots as 0
    $magicSquare;
    for ($i = 0; $i < $n; $i++)
        for ($j = 0; $j < $n; $j++)
            $magicSquare[$i][$j] = 0;
 
    // Initialize position for 1
    $i = (int)$n / 2;
    $j = $n - 1;
 
    // One by one put all values in
    // magic square
    for ($num = 1; $num <= $n * $n; )
    {
         
        // 3rd condition
        if ($i == -1 && $j == $n)
        {
            $j = $n-2;
            $i = 0;
        }
        else
        {
            // 1st condition helper if
            // next number goes to out
            // of square's right side
            if ($j == $n)
                $j = 0;
 
            // 1st condition helper if
            // next number is goes to
            // out of square's upper
            // side
            if ($i < 0)
                $i = $n-1;
        }
         
        // 2nd condition
        if ($magicSquare[$i][$j])
        {
            $j -= 2;
            $i++;
            continue;
        }
        else
         
            // set number
            $magicSquare[$i][$j] = $num++;
 
        // 1st condition
        $j++; $i--;
    }
 
    // Print magic square
    echo "The Magic Square for n = " . $n
        . ":\nSum of each row or column "
        . $n * ($n * $n + 1) / 2;
         
    echo "\n\n";
    for ($i = 0; $i < $n; $i++)
    {
        for ($j = 0; $j < $n; $j++)
            echo $magicSquare[$i][$j] . " ";
        echo "\n";
    }
}
 
// Driver program to test above function
 
// Works only when n is odd
$n = 7;
generateSquare ($n);
     
// This code is contributed by mits.
?>

Javascript

<script>
 
// javascript program to generate odd sized magic squares
   // Function to generate odd sized magic squares
 
function generateSquare(n)
{
    magicSquare = Array(n).fill(0).map(x => Array(n).fill(0));
 
    // Initialize position for 1
    var i = parseInt(n / 2);
    var j = n - 1;
 
    // One by one put all values in magic square
    for (num = 1; num <= n * n;) {
        if (i == -1 && j == n) // 3rd condition
        {
            j = n - 2;
            i = 0;
        }
        else {
            // 1st condition helper if next number
            // goes to out of square's right side
            if (j == n)
                j = 0;
 
            // 1st condition helper if next number is
            // goes to out of square's upper side
            if (i < 0)
                i = n - 1;
        }
 
        // 2nd condition
        if (magicSquare[i][j] != 0) {
            j -= 2;
            i++;
            continue;
        }
        else
            // set number
            magicSquare[i][j] = num++;
 
        // 1st condition
        j++;
        i--;
    }
 
    // print magic square
    document.write("The Magic Square for " + n
                       + ":<br>");
    document.write("Sum of each row or column "
                       + parseInt(n * (n * n + 1) / 2) + ":<br>");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            document.write(magicSquare[i][j] + " ");
        document.write("<br>");
    }
}
 
// driver program
 // Works only when n is odd
var n = 7;
generateSquare(n);
 
// This code is contributed by 29AjayKumar
 
</script>
Producción

The Magic Square for n=7:
Sum of each row or column 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 

Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n 2 )

NOTA: Este enfoque solo funciona para valores impares de n.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *