Problema del cuadrado mágico en C++

1. Problema del cuadrado mágico
2. Implementación del Cuadrado Mágico en C++

Este artículo explicará el problema del cuadrado mágico, sus propiedades y su implementación usando C++. Aprendamos el problema del cuadrado mágico para implementar el cuadrado mágico.

Problema del cuadrado mágico

Un cuadrado mágico es una matriz 2D de números enteros positivos en la que la suma de cada fila, columna y diagonal es la misma. La suma a menudo se llama Suma Mágica, que se refiere a una suma constante en cada fila, columna y diagonal.

El valor entero en cada ubicación del cuadrado mágico debe ser único. Si N es del tamaño de un cuadrado mágico, puede contener números enteros del 1 al N².

La siguiente fórmula calcula la suma mágica.

El tamaño del cuadrado mágico indicaría el número de filas y columnas. Si N es igual a 3, el cuadrado mágico tendrá tres filas y tres columnas.

Ahora, expliquemos la suma mágica con un ejemplo. Supongamos que el valor de N es 3, entonces por la fórmula anterior, se puede calcular como:

Aquí, 15 es la suma mágica. Implica que la suma de cada columna, fila y diagonal debe ser igual a 15.

El cuadrado mágico con un tamaño igual a 3 se muestra en la siguiente figura.

Podemos ver que cada fila, columna y suma diagonal es igual a la suma mágica, y cada entrada es única.

Después de entender el problema del cuadrado mágico, ahora vamos a implementarlo.

Que el tamaño del cuadrado mágico que implementaremos sea n. Luego, el primer valor (es decir, 1) se almacena en la posición (n/2,n-1) en el cuadrado mágico.

Supongamos que esta ubicación es (i,j), luego el siguiente valor estará en la posición (i-1,j+1). Aquí asumimos que todas las filas y columnas tienen un estilo envolvente (es decir, también conocido como forma circular).

Condiciones para el problema del cuadrado mágico

1. La ubicación del siguiente valor se determina sumando 1 al número de columna actual y restando 1 del número de fila actual.
   • Si la nueva ubicación de la columna se convierte en n, entonces se ajustará a 0 ya que las columnas y las filas son circulares.
   • Del mismo modo, si la nueva ubicación del cuervo se convierte en -1, se ajustará a n-1.
2. Suponga que la ubicación recién calculada ya contiene un valor. En ese caso, el número de fila actual se actualizará agregando 1, y el número de columna actual se actualizará restando 2 de él.
3. Si el número de columna recién calculado es n y el número de fila es -1, entonces la ubicación actualizada será (0,n-2).

Implementación del Cuadrado Mágico en C++

Veamos el siguiente código antes de pasar a los detalles:

#include <bits/stdc++.h>
using namespace std;
// This function will generate an old-size magic square only.
void magicSquareGenerator(int s) {
  int magic_Square[s][s];
  // This will initialize all locations of the magic square to 0
  memset(magic_Square, 0, sizeof(magic_Square));
  // here, r is the row index, and c is the column index for the first number
  int r = s / 2;
  int c = s - 1;
  //  generating magic square
  for (int num = 1; num <= s * s;) {
    if (r == -1 && c == s)  // Third condition
    {
      c = s - 2;
      r = 0;
    } else {
      if (c == s) c = 0;
      if (r < 0) r = s - 1;
    }
    if (magic_Square[r][c])  // second condition
    {
      c -= 2;
      r++;
      continue;
    } else
      magic_Square[r][c] = num++;
    c++;
    r--;  // 1st condition
  }

  // Print magic square
  cout << "The Magic Square has:" << s << " rows and " << s << " columns.";
  cout << "\nThe Magic Sum is: " << s * (s * s + 1) / 2 << ":\n";
  for (r = 0; r < s; r++) {
    for (c = 0; c < s; c++)
      // displaying the magic square.
      cout << setw(4) << magic_Square[r][c] << " ";
    cout << endl;
  }
}

int main() {  // Code expects only odd sizes
  int s;
  cout << "Enter the size of the Magic Square: ";
  cin >> s;
  while (s % 2 == 0) {
    cout << "Plz Enter an odd number :" << endl;
    cout << "Enter the size of the Magic Square: ";
    cin >> s;
  }
  magicSquareGenerator(s);
  return 0;
}

Aquí hay una explicación paso a paso del programa del cuadrado mágico anterior.

1. La ubicación del valor 1 es = (3/2,3-1) = (1,2) = [1][2].
2. La ubicación del valor 2 es = (1-1,2+1) = (1,2) = [1][2].
3. La ubicación del valor 3 es = (0-1,0+1) = (3-1,1+1) = [2][1].
4. La ubicación del valor 4 es = (2-1,1+1) = (1,2) = [1][2].
   • Como [1][2] ya tiene valor 1 entonces, por condición 2, una nueva ubicación será (1+1,2-2) = [2][0].
5. La ubicación del valor 5 es = (2-1,0+1) = (1,1) = [1][1].
6. La ubicación del valor 6 es = (1-1,1+1) = (1,2) = [0][2].
7. La ubicación del valor 7 es = (0-1,2+1) = (-1,3)
   • La condición 3 se cumple, por lo que la nueva ubicación será (0,3-2)=[0][1].
8. La ubicación del valor 8 es = (0-1,1+1) = (-1,2) = [2][2] ya que por condición se envuelve 1 fila.
9. La ubicación del valor 9 es = (2-1,2+1) = (1,3) = [1][0] ya que la condición 1 columna está envuelta.

Aquí está el resultado cuando ingresamos el tamaño del cuadrado mágico 3.

Enter the size of the Magic Square: 3
The Magic Square has:3 rows and 3 columns.
The Magic Sum is: 15:
   2    7    6
   9    5    1
   4    3    8

Aquí está el resultado cuando ingresamos el tamaño del cuadrado mágico 7.

Enter the size of the Magic Square: 7
The Magic Square has:7 rows and 7 columns.
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

Nota: El programa anterior solo funciona cuando ingresamos el tamaño impar del cuadrado mágico.

La complejidad temporal y espacial del algoritmo propuesto es $O(n^2)$.