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.

• Falco: Even without Sets he could use a c = bool[len*len] and loop once over the whole square and first check if the corresponding entry is already true and then set c[square[i][j]] = true - effectively using a simple array as a more efficient Set for this case.
• tieskedh: @Falco, if you're refering to duplicated values, you're correct. (Didn't provide implementation because it's a homework excercise...). But, what it square has very big numbers?
• qwerty: What if I store the fields in a one dimensional array,call Arrays.sort() and then iterate to determine if any consecutive values are equal? Is that what you were referring to in your answer, and would that be faster than the system I'm using now?
• tieskedh: My first suggesiton... Go with the other answers as their algorithms are way better. I was sugesting how you could improve your alorithm a little bit: If your first coordinate == your second coordinate, you don't need to check that first coordinate anymore any further. So in short, you can update your continue to continue the 2nd loop.

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).

• qwerty: Although I use four nested for loops, each set of two iterates through the array once, because it is a 2D array. Therefore, unless I am mistaken, the cost is O(n^2). Either way, your point is valid.
• Clearer: I was thinking in terms of n = length, but yes, you're right. I didn't use n = length for the other examples :-) I fixed it

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).

• qwerty: Would this use less processing power? Perhaps the underlying code in the Set.add() method uses a for loop? I'm not sure, I really don't know how all this Hash stuff works, but this question thread has given me a lot to Google about.
• palin dromo: @a p, yes. Your solution is O(n^4) and this one is O(n^2). I'm pretty sure the underlying code does not use a loop (haven't checked though, I leave that for the flat-earthers).
• qwerty: I just want to make sure we're not crossing wires. As @Clearer pointed out, my solution is O(n^4) in terms of n = length, however, based on the absolute length of the array, it is only O(n^2). With that in mind, would the new method suggested here still be faster? In terms of absolute length, is it O(n)?
• palin dromo: Yes. HashSet.add() is O(1). Whichever way you measure the outer loops, a hash will always be faster in O() terms than a loop
• Mast: You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) in the answer so that the author and other readers can learn from your thought process.