ISC Practicals and Theory - Magic Square (OOP)

A magic square is a square matrix whose rows, columns and both diagonals all have the same sum. This version is written as a class MagicSquare with data members, a parameterised constructor and methods that each do one job; main reads the order, creates an object and calls the methods to print the matrix and say whether it is a magic square.

Definition

An $n \times n$ matrix is a magic square (classic definition) if every row, every column and both diagonals have the same sum, and the matrix contains each of $1, 2, \ldots, n^2$ exactly once. The magic sum is $\dfrac{n(n^2+1)}{2}$: 15 for $n = 3$, 34 for $n = 4$.

Example: for $n = 4$, the matrix with rows 16 3 2 13, 5 10 11 8, 9 6 7 12, 4 15 14 1 uses 1 to 16 once each and every row, column and diagonal adds up to 34.

The program enforces both conditions, so a matrix with equal sums but repeated values (for example all 5s) is not accepted. A $2 \times 2$ matrix can never be a classic magic square.

Algorithm

1. main reads the order into size. If it is less than 2 or more than 10, it prints Invalid size and stops.
2. Otherwise main creates ob with new MagicSquare(size). The parameterised constructor stores the order in n and creates the array a[n][n].
3. readMatrix(sc) reads the elements with two nested loops, and display() prints them.
4. check() calls usesAllNumbers(), which counts each value in the array seen and returns false if a value is outside 1 to n * n or occurs twice.
5. If that is false, check() prints that the elements are not 1 to n * n without repetition.
6. Otherwise check() calls sumsEqual():
   • diagSum(1) (main diagonal) is the target;
   • diagSum(2) (right diagonal), every rowSum(i) and every colSum(i) must equal it.
7. If sumsEqual() is false, check() prints that the sums are not equal; otherwise it prints Magic square and the sum.

Program

The constructor creates the array, readMatrix() fills it, rowSum(), colSum() and diagSum() each return one sum, sumsEqual() and usesAllNumbers() test the two conditions and check() prints the verdict.

import java.util.Scanner;

/**
 * Class MagicSquare checks whether an n x n matrix is a magic square.
 * Classic definition used here: all rows, all columns and both diagonals
 * have the same sum, and the matrix contains each of 1, 2, ..., n*n exactly once.
 */
public class MagicSquare
{
    int a[][];      // stores the elements of the matrix
    int n;          // order of the square matrix (number of rows = number of columns)

    /**
     * Parameterised constructor: stores the order and creates the array.
     * Parameter nn: the order of the matrix.
     */
    MagicSquare(int nn)
    {
        n = nn;
        a = new int[n][n];
    }

    /**
     * Reads the elements of the matrix.
     * Parameter sc: the Scanner object that reads from the keyboard.
     */
    void readMatrix(Scanner sc)
    {
        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();
            }
        }
    }

    /**
     * Prints the matrix row by row.
     */
    void display()
    {
        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
        }
    }

    /**
     * Returns the sum of the elements of row r.
     * Parameter r: the row number (0 to n-1).
     */
    int rowSum(int r)
    {
        int s = 0;
        for (int j = 0; j < n; j++)
        {
            s = s + a[r][j];
        }
        return s;
    }

    /**
     * Returns the sum of the elements of column c.
     * Parameter c: the column number (0 to n-1).
     */
    int colSum(int c)
    {
        int s = 0;
        for (int i = 0; i < n; i++)
        {
            s = s + a[i][c];
        }
        return s;
    }

    /**
     * Returns the sum of the main (left) diagonal when flag is 1,
     * or of the right diagonal when flag is 2.
     */
    int diagSum(int flag)
    {
        int s = 0;
        for (int i = 0; i < n; i++)
        {
            if (flag == 1)
            {
                s = s + a[i][i];                    // main diagonal: row = column
            }
            else
            {
                s = s + a[i][n - 1 - i];            // right diagonal: row + column = n - 1
            }
        }
        return s;
    }

    /**
     * Returns true if every row, every column and both diagonals
     * have the same sum.
     */
    boolean sumsEqual()
    {
        int target = diagSum(1);                    // sum of the main diagonal is the reference
        if (diagSum(2) != target)
        {
            return false;
        }
        for (int i = 0; i < n; i++)
        {
            if (rowSum(i) != target || colSum(i) != target)
            {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns true if the matrix holds each of 1, 2, ..., n*n exactly once.
     */
    boolean usesAllNumbers()
    {
        int seen[] = new int[n * n + 1];            // seen[v] counts how many times v occurs
        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
                {
                    return false;
                }
                seen[a[i][j]]++;
                if (seen[a[i][j]] > 1)              // repeated value
                {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Prints whether the matrix is a magic square, with the magic sum if it is.
     */
    void check()
    {
        if (!usesAllNumbers())
        {
            System.out.println("Not a magic square (elements are not 1 to " + (n * n) + " without repetition)");
        }
        else if (!sumsEqual())
        {
            System.out.println("Not a magic square (sums are not equal)");
        }
        else
        {
            System.out.println("Magic square, sum = " + diagSum(1));
        }
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);        // reads from the keyboard
        System.out.print("Enter the order n: ");
        int size = sc.nextInt();                    // order entered by the user
        if (size < 2 || size > 10)                  // order must lie between 2 and 10
        {
            System.out.println("Invalid size");
        }
        else
        {
            MagicSquare ob = new MagicSquare(size); // object of the class
            ob.readMatrix(sc);
            ob.display();
            ob.check();
        }
    }
}

Variable description table

Sample input and output

Enter the order n: 4
Enter the elements:
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1
Matrix:
16	3	2	13	
5	10	11	8	
9	6	7	12	
4	15	14	1	
Magic square, sum = 34

Enter the order n: 2
Enter the elements:
1 2
3 4
Matrix:
1	2	
3	4	
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: 11
Invalid size

Dry run

Take the $4 \times 4$ matrix with rows 16 3 2 13, 5 10 11 8, 9 6 7 12, 4 15 14 1 (the first sample). Here size = 4, so the constructor makes a $4 \times 4$ array and seen has 17 places.

usesAllNumbers() finds all sixteen values between 1 and 16 with none repeated, so it returns true. Then sumsEqual() works out the sums:

Every sum equals 34, so check() prints Magic square, sum = 34, 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."