Monthly Archives: October 2020

Magic Square

<< Previous Article

A magic square is a square, with n rows and n columns, and thus consisting of n2 smaller squares. Moreover, each of these squares are filled with a distinct number, such that the sum of all the numbers in a row is equal to the sum of all the numbers in any other row or column. If n is even, it may not be always possible to form such a magic square, e.g. there exists no magic square for n = 2. However, if n is odd, there are infinitely many magic squares possible for all such n. To restrict this infinitely many to a finite number, the n2 squares are typically filled with the consecutive numbers 1, 2, …, n2. Once a magic square is obtained using these numbers, then by adding any integer to all of the squares, one may obtain yet another magic square. And thus, as integers are infinite, there is an infinite number of possible magic squares for a given n.

Interestingly enough, for an odd n, there exists a simple logic to fill the numbers 1, 2, …, n2 into a n x n magic square. Consequently, the sum of any row or column turns out to be n * (n2 + 1) / 2. And the middle most number turns out to be (n2 + 1) / 2. Here is the logic to fill the numbers 1, 2, …, n2, in that order:

  • Fill 1 in middle most square of the first row
  • For every next number, follow the steps below:
    • If the current number is filled in the first row, then fill the next number in the last row, in the column just next to the current one. If it is not applicable or possible, follow the next step.
    • If the current number is filled in the last column, then fill the next number in the first column, in the row just above the current one. If it is not applicable or possible, follow the next step.
    • Fill in the row just above the current one in the just next column. If it is not applicable or possible, follow the next step.
    • Fill in the row just below the current one in the same column. If all the above fails, this will be always possible.

In a more programmatic format, it would look like this, assuming the magic square to be a 2-D array of size n x n, with its index starting from 0:

magic_square(int M[n][n])
{
	r = 0; // current row
	c = (n - 1) / 2; // current column

	for (i = 1; i <= n * n; i++)
	{
		M[r][c] = i;
		if ((r == 0) && (c < (n - 1)))
		{
			nr = n - 1;
			nc = c + 1;
		}
		else if ((c == (n - 1)) && (r > 0))
		{
			nr = r - 1;
			nc = 0
		}
		else if ((r > 0) && (c < (n - 1)))
		{
			nr = r - 1;
			nc = c + 1;
		}
		else // ((r == 0) && (c == (n - 1)))
		{
			r = r + 1;
			c = c;
			continue; // as this is always possible
		}
 		if (!isfilled(M[nr][nc]))
		{
			r = nr;
			c = nc;
		}
		else
		{
			r = r + 1;
			c = c;
		}
	}
}

On a closer observation, the statements in the first three conditionals of the first if … else above are identical with modulo n (% n), i.e. they are same as:

nr = (r - 1 + n) % n;
nc = (c + 1) % n;

and the logic of the last else in both the above if … else are identical.
Hence, the logic can be further compacted as follows:

magic_square(int M[n][n])
{
	r = 0; // current row
	c = (n - 1) / 2; // current column

	for (i = 1; i <= n * n; i++)
	{
		M[r][c] = i;
		nr = (r - 1 + n) % n;
		nc = (c + 1) % n;
 		if (!isfilled(M[nr][nc]))
		{
			r = nr;
			c = nc;
		}
		else
		{
			r = r + 1;
			c = c;
		}
	}
}

Here’s 5 x 5 magic square to understand the above logic:

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

Next Article >>

   Send article as PDF