Determining if a given square is a magic square

Question

I'm writing the following program for a school assignment. The prompt is as follows:

A magic square is square grid filled with distinct positive integers such that each cell contains a different integer and the sum of the integers in each row, column and diagonal is equal.

My task is to make a boolean method, named magical() that is passed a 2d array, and will return true if those criteria are met. This is the code I wrote:

private static boolean magical(int[][] square) {
        int length = square.length;
        //This loop checks for duplicate values
        for (int i = 0; i < length; i++){
            for (int j = 0; j < length; j++){
                int x = square[i][j];
                for (int a = 0; a < length; a++){
                    for (int b = 0; b < length; b++){
                        if (a == i && b == j) continue;
                        if (x == square[a][b]) return false;
                    }
                }
            }
        }
        ArrayList<Integer> sums = new ArrayList<>();
        //This loop finds the sums of the rows and columns
        for (int i = 0; i < length; i++){
            int sum = 0;
            int sum2 = 0;
            for (int j = 0; j < length; j++){
                sum += square[i][j];
                sum2 += square[j][i];
            }
            sums.add(sum);
            sums.add(sum2);
        }
        //The next two loops find the sums of each diagonal. 
        int x = 0;
        int y = 0;
        int sum = 0;
        while (x < length && y < length){
            sum += square[x][y];
            x++;
            y++;
        }
        sums.add(sum);
        sum = 0;
        x = 0;
        y = length - 1;
        while (x < length && y >= 0){
            sum += square[x][y];
            x++;
            y--;
        }
        sums.add(sum);
        return sums.stream().allMatch(s -> s.equals(sums.get(0)));
    }

Here are my questions:

1. Is there any way to confirm that there are no duplicate values in the array without having to nest four for loops? This seems like an incredibly inefficient system.

2. Is there any way to combine the two loops in the end that are used to make sure that the sum of values in each diagonal are the same? I am currently using two loops, but seeing as I am iterating through the same array, it seems inefficient to do it twice.

I am also open to any other suggestions you may have. Please note, it is given in the prompt that all arrays passed as parameters will be squares, and it is not required to test for this.

Answer 1

Answering your first question, yes there is a better way. Efficiency doesn't matter in your case but in this instance the more efficient thing is also easier on the eyes.

The usual idea would be to make a hash set of the elements, then you have O(1) look up of whether you have already inserted an elements, making the task O(n^2).

I'm not that familiar with Java sadly so to answer your second question I just propose the fairly imperative thing of doing everything in one traversal (I think probably it can be done with the functional constructs that Java has), like so.

private static boolean magical(int[][] square) {
    Set<Integer> seenInts = new HashSet<>();
    var leftDiagonalSum = 0;
    var rightDiagonalSum = 0;
    var rowSums = new int[square.length];
    var colSums = new int[square.length];

    for(var i = 0; i < square.length; i++) {
        for(var j = 0; j < square.length; j++) {
            var currentElement = square[i][j];

            seenInts.add(currentElement);
            leftDiagonalSum += (i == j) ? currentElement : 0;
            rightDiagonalSum += (i == square.length - 1 - j) ? currentElement : 0;
            rowSums[i] += currentElement;
            colSums[j] += currentElement;
        }
    }

    Set<Integer> sumSet = new HashSet<>();

    sumSet.add(leftDiagonalSum);
    sumSet.add(rightDiagonalSum);

    for(var i = 0; i < square.length; i++) {
        sumSet.add(rowSums[i]);
        sumSet.add(colSums[i]);
    }

    var noDuplicates = seenInts.size() == square.length * square.length;
    var allSameSums = sumSet.size() == 1;

    return noDuplicates && allSameSums;
}

Edit - While I may not know much Java, there's no reason to specify the implementation of Set used, so the type of seenInts and sumSet can just be Set

Answer 2

Note, using Sets, is the way to go. My answer is based upon the assumption that you didn't learn about Sets and you can only use arrays.

duplicated values

A1 A2 A3
A4 A5 A6
A7 A8 A9

your loop:

for (int i = 0; i < length; i++){
    for (int j = 0; j < length; j++){
        int x = square[i][j];
        for (int a = 0; a < length; a++){
             for (int b = 0; b < length; b++){
                 if (a == i && b == j) continue;
                 if (x == square[a][b]) return false;
             }
        }
    }
}

In this loop, you will check everything twice...
For example:
square[i][j] will point to A9 and square[a][b] will point to A1.
but, also reversed: square[a][b] will point to A9 and square[i][j] will point to A1.
Therefor, you check A1 with A9 twice (and every other combination as well).

diagonals

You can use one variable instead of both x and y

Answer

1. for every coordinate (2 loops) you want to check the other coordinates (2 loops). This means you need 4 loops.
   You could store the fields in a 1 dimensional array first, but to my knowledge, this wouldn't be any quicker.
2. after rewriting using 1 variable, you can answer this question yourself.

Answer 3

My java is a bit rusty, so my answer is going to be more generic than just java.

For 1., as @tieskedh points out, you want to use sets. If you don't have to available, you can emulate one by creating a list containing all the elements, sorting it and checking that none of the values has a neighbour that is identical to itself. This will be effecient and easy to understand; the cost is O(n) for the copy, O(n log n) for the sort and O(n) for the comparison. In terms of big-O notation, you won't do better than that. In contrast, your current solution is O(n^2).

For 2. I probably wouldn't do it. Expressiveness is very important to code quality and combining two loops to save a few cycles may not be a good idea. It might also decrease performance if you end up trashing your cache. This particular problem seems like a prime candidate for poor performance, due to caching issue if you do combine the loops. Others have already pointed out that you only need one variable to access the elements you want. You should replace your while-loops with for-loops. Both because a for-loop expresses your intent better, but also because you can remove a lot of the polution your variables introduce. Consider how you might be able to move it into a function, that will allow you to do both loops with the same code (hint; use step variables for x and y as parameters to your function).

Answer 4

I'll have a go at your first question, using a Set:

Set<Integer> seenNumbers = new HashSet<Integer>();
for (int i = 0; i < length; ++i) {
    for (int j = 0; j < length; ++j) {
        if (!seenNumbers.add(square[i][j])) {

            return false;
        }
    }
}

... rest of method

It keeps adding elements to the Set until it finds a duplicate (Set.add() returns false when the element is already in the Set).