ISC Practicals and Theory - Magic Square

A magic square is a square matrix in which every row, every column and both diagonals add up to the same number. This program, written in the main method alone, reads an $n \times n$ matrix, checks the order, prints the matrix and tells whether it is a magic square.

Definition

In the classic definition, an $n \times n$ matrix is a magic square if:

• all $n$ rows, all $n$ columns and the two diagonals have the same sum, and
• it contains each of the numbers $1, 2, \ldots, n^2$ exactly once.

The common sum is called the magic sum. For order $n$ it is $\dfrac{n(n^2+1)}{2}$, which is 15 for $n = 3$ and 34 for $n = 4$.

Example: the matrix with rows 2 7 6, 9 5 1, 4 3 8 uses 1 to 9 once each, every row, column and both diagonals add up to 15, so it is a magic square.

This program enforces both conditions. A matrix such as three rows of 5 5 5 has equal sums everywhere but repeats a value, so the program says it is not a magic square.

A $2 \times 2$ matrix can never be a classic magic square (the numbers 1 to 4 cannot be placed to give equal sums), but the program still accepts order 2 and reports it as not magic.

Algorithm

1. Read the order n. If it is not from 2 to 10, print Invalid size and stop.
2. Create the square array a, read the elements row by row and print the matrix.
3. Check the values: the array seen of size n * n + 1 counts how many times each value occurs. If any element is outside 1 to n * n, or a value occurs twice, set allUsed = false. If allUsed is false, print that the elements are not 1 to n * n without repetition, and stop.
4. Find the sum of the main diagonal, target, adding a[i][i] (row = column). Find the sum of the right diagonal, right, adding a[i][n - 1 - i] (row + column = n - 1). Set equal = (right == target).
5. For every i, find the sum of row i (rowSum) and of column i (colSum). If either differs from target, set equal = false.
6. If equal is false, print that the sums are not equal. Otherwise print Magic square with the sum target.

Program

Everything is written inside main: the input, the display, the check of the values, the two diagonals and the loop that adds each row and column.

import java.util.Scanner;
public class MagicSquare
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);        // reads from the keyboard
        System.out.print("Enter the order n: ");
        int n = sc.nextInt();                       // order of the square matrix (number of rows = number of columns)
        if (n < 2 || n > 10)                        // order must lie between 2 and 10
        {
            System.out.println("Invalid size");
        }
        else
        {
            int a[][] = new int[n][n];              // create the square array
            System.out.println("Enter the elements:");
            for (int i = 0; i < n; i++)             // i moves over the rows
            {
                for (int j = 0; j < n; j++)         // j moves over the columns
                {
                    a[i][j] = sc.nextInt();
                }
            }
            System.out.println("Matrix:");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    System.out.print(a[i][j] + "\t");
                }
                System.out.println();               // new line after each row
            }
            int seen[] = new int[n * n + 1];        // seen[v] counts how many times v occurs
            boolean allUsed = true;                 // stays true while the values are 1 to n*n without repetition
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (a[i][j] < 1 || a[i][j] > n * n)     // value outside 1 to n*n
                    {
                        allUsed = false;
                    }
                    else
                    {
                        seen[a[i][j]]++;
                        if (seen[a[i][j]] > 1)              // repeated value
                        {
                            allUsed = false;
                        }
                    }
                }
            }
            if (!allUsed)
            {
                System.out.println("Not a magic square (elements are not 1 to " + (n * n) + " without repetition)");
            }
            else
            {
                int target = 0;                     // sum of the main diagonal is the reference
                int right = 0;                      // sum of the right diagonal
                for (int i = 0; i < n; i++)
                {
                    target = target + a[i][i];          // main diagonal: row = column
                    right = right + a[i][n - 1 - i];    // right diagonal: row + column = n - 1
                }
                boolean equal = (right == target);  // stays true while all the sums are equal
                for (int i = 0; i < n; i++)
                {
                    int rowSum = 0, colSum = 0;     // sums of row i and of column i
                    for (int j = 0; j < n; j++)
                    {
                        rowSum = rowSum + a[i][j];
                        colSum = colSum + a[j][i];
                    }
                    if (rowSum != target || colSum != target)
                    {
                        equal = false;
                    }
                }
                if (!equal)
                {
                    System.out.println("Not a magic square (sums are not equal)");
                }
                else
                {
                    System.out.println("Magic square, sum = " + target);
                }
            }
        }
    }
}

Variable description table

Sample input and output

Enter the order n: 3
Enter the elements:
2 7 6
9 5 1
4 3 8
Matrix:
2	7	6	
9	5	1	
4	3	8	
Magic square, sum = 15

Enter the order n: 3
Enter the elements:
1 2 3
4 5 6
7 8 9
Matrix:
1	2	3	
4	5	6	
7	8	9	
Not a magic square (sums are not equal)

Enter the order n: 3
Enter the elements:
5 5 5
5 5 5
5 5 5
Matrix:
5	5	5	
5	5	5	
5	5	5	
Not a magic square (elements are not 1 to 9 without repetition)

Enter the order n: 1
Invalid size

Dry run

Take the matrix with rows 2 7 6, 9 5 1, 4 3 8 (the first sample), so n = 3.

First the program checks the values: all nine are between 1 and 9 and no value is counted twice, so allUsed stays true. Then it finds the sums:

Every sum equals the target, so equal stays true and the program prints Magic square, sum = 15, the same as the first sample run.

Variations

1. Generate a magic square "Generate an odd-order magic square of size n x n using the Siamese method and display it."
2. Equal sums only "Check whether the sum of every row, every column and both diagonals of a matrix is the same."
3. Sums of a matrix "Display the sum of each row, each column and each diagonal of a square matrix."