Magic Square Problem in C++

1. Magic Square Problem
2. Implementation of the Magic Square in C++

This article will explain the magic square problem, its properties, and its implementation using C++. Let’s learn the magic square problem to implement the magic square.

Magic Square Problem

A magic square is a 2D array of positive integers in which the sum of each row, column, and diagonal is the same. The sum is often called Magic Sum, which refers to a constant sum in each row, column, and diagonal.

The integer value in each location of the magic square must be unique. If N is the size of a magic square, it can contain integers from 1 to N².

The following formula calculates the magic sum.

The size of the magic square would indicate the number of rows and columns. If N equals 3, the magic square will have three rows and three columns.

Now, let’s explain magic sum with an example. Suppose that the value of N is 3, then by the above formula, it can be calculated as:

Here, 15 is the magic sum. It implies that each column, row, and diagonal sum should equal 15.

The magic square with a size equal to 3 is shown in the figure below.

We can see that each row, column, and diagonal sum is equal to the magic sum, and every entry is unique.

After understanding the magic square problem, now let’s implement it.

Let the size of the magic square we will implement be n. Then, the first value (i.e., 1) is stored at position (n/2,n-1) in the magic square.

Suppose this location is (i,j), then the next value will be at position (i-1,j+1). Here we assume that every rows and column have a wrap-around (i.e., also known as circler fashion).

Conditions for the Magic Square Problem

1. The location of the next value is determined by adding 1 to the current column number and subtracting 1 from the current row number.
   • If the new location of the column becomes n, then it will be wrapped to 0 as columns and rows are in a circular manner.
   • Similarly, If the new location of the crow becomes -1, it will be wrapped to n-1.
2. Suppose the newly calculated location already contains a value. In that case, the current row number will be updated by adding 1, and the current column number will be updated by subtracting 2 from it.
3. If the newly calculated column number is n and the row number is -1, then the updated location will be (0,n-2).

Implementation of the Magic Square in C++

Let’s look at the below code before jumping into the details:

#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;
}

Here is a step-by-step explanation of the above magic square program.

1. Location of value 1 is = (3/2,3-1) = (1,2) = [1][2].
2. Location of value 2 is = (1-1,2+1) = (1,2) = [1][2].
3. Location of value 3 is = (0-1,0+1) = (3-1,1+1) = [2][1].
4. Location of value 4 is = (2-1,1+1) = (1,2) = [1][2].
   • As [1][2] already have value 1 so, by condition 2, a new location will be (1+1,2-2) = [2][0].
5. Location of value 5 is = (2-1,0+1) = (1,1) = [1][1].
6. Location of value 6 is = (1-1,1+1) = (1,2) = [0][2].
7. Location of value 7 is = (0-1,2+1) = (-1,3)
   • Condition 3 holds, so the new location will be (0,3-2)=[0][1].
8. Location of value 8 is = (0-1,1+1) = (-1,2) = [2][2] as by condition 1 row is wrapped.
9. Location of value 9 is = (2-1,2+1) = (1,3) = [1][0] as by condition 1 column is wrapped.

Here is the output when we enter the size of the magic square 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

Here is the output when we enter the size of the magic square 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

Note: The above program only works when we input the odd size of the magic square.

The time and space complexity of the proposed algorithm is $O(n^2)$.