Magic Square test in Java

In recreational mathematics, a magic square is an arrangement of numbers in a square grid, where the numbers in each row, and in each column, and the numbers in the forward and backward main diagonals, all add up to the same number. For example, a 3×3 magic square is as follows:

4 9 2
3 5 7
8 1 6

The sum of all rows, columns and diagonals is 15.

In this post I will demonstrate how to develop a program in Java programming language to determine if the numbers stored in a a square integer array form a magic square or not. This question was asked in the Computer Science Paper 2 (Practical) in the year 2005, however, it was referred to by the name wondrous square instead of magic square.

A square of size nxn will by filled by numbers from 1 to n2. The sum of first k natural number is given by the formula k(k+1)/2. In this case k=nand therefore sum would be n2(n2+1)/2. Now this sum is to be evenly distributed among n rows/columns hence sum of individual row/columns/diagonal would be [n2(n2+1)/2]/n. This is called magic constant or magic sum denoted by M.

The logic is essentially to check if the sum of each row, column and diagonal is equal to M or not. The program can be made slightly more efficient if we check for rows, columns and diagonals in one set of nested loop.

We must also ensure that only numbers from 1 to n2 are used and each number is used only once. This we will accomplish using a boolean array of size n2 for storing the repetition status of each number. For example index position 0 will store the status of number 1, that is false till it’s not found and true as soon as it’s found. If the status is already true when 1 is found it will indicate repetition.

The Java program for the above logic would be as follows:

class Magic{
    public static boolean isMagicSquare(int[][] arr){
        final int n=arr.length;
        final int nSquare=n*n;
        final int M=(n*n*(n*n+1)/2)/n;
        int sumOfRow=0, sumOfColoumns=0, sumOfPrimaryDiagonal=0, sumOfSecondaryDiagonal=0;
        boolean[] flag= new boolean[n*n];
        for(int row=0; row<n; row++){
            sumOfRow=0;
            sumOfColoumns=0;
            for(int col=0; col<n; col++){
                if(arr[row][col]<1 || arr[row][col]>nSquare) return false;
                if(flag[arr[row][col]-1]==true) return false;
                flag[arr[row][col]-1]=true;
                sumOfRow += arr[row][col];
                sumOfColoumns += arr[col][row];
            }
            sumOfPrimaryDiagonal += arr[row][row];
            sumOfSecondaryDiagonal += arr[row][n-row-1];
            if(sumOfRow!=M || sumOfColoumns!=M) return false;
        }
        if(sumOfPrimaryDiagonal!=M || sumOfSecondaryDiagonal!=M) return false;
        return true;
    }
    public static void main(String []args){
        int[][] a ={{4,9,2},
                    {3,5,7},
                    {8,1,6}};
        System.out.println(isMagicSquare(a));
    }
}

Students should note that there is only one set of nested loop and calculation of diagonals is done in the outer loop for the sake of efficiency. Another thing to be noticed is use of boolean array flag to detect the repetition of numbers without the use of another set of nested loop. Note that the above code will give correct answer even if we remove the boolean array and the associated code because the sum would not be equal to M in case there is repetition, however, the program would be slightly slower since false would be returned after a lot of iterations. Also note that the question asked in the ISC Practical of 2005 explicitly  mentioned that each integer appears only once. As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.

3 thoughts on “Magic Square test in Java

  1. Pingback: Magic square | www.VinaySingh.info

  2. Jeet Trivedi

    Hello Sir

    I didn’t get below portion of the above program

    if(flag[arr[row][col]-1]==true) return false;
    flag[arr[row][col]-1]=true;

    Reply
    1. Vinay Singh Post author

      The purpose of the boolean array flag is to store whether any given integer in the range 1 to n2 has already been encountered or not. The portion ‘arr[row][col]’ is the number we are trying to find i.e. if it has been already encountered or not. The -1 after ‘arr[row][col]’ (i.e. arr[row][col]-1 ) is an adjustment because our flag array is starting from 0 and out range is starting from 1. Therefore if the condition ‘flag[arr[row][col]-1]==true’ is true it means that the number ‘arr[row][col]’ has already been encountered. The following line (flag[arr[row][col]-1]=true;) set the flag to true so that it can be tested for repetition later on.

      Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.