Speed up Magic square program

Question

I have written a Java program to calculate magic squares with recursion and backtracking. A 3*3 Magic square is calculated in about 1 sec, but a 4*4 needs about 50 minutes on my laptop with Intel i5. How i can improve the performance?

import java.util.Scanner;

public class MagicSquare {

private byte[][] square;
private byte magicNumber;
private long tmp = 0;

public MagicSquare() {

    Scanner sc = new Scanner(System.in);
    byte size = sc.nextByte();
    square = new byte[size][size];
    sc.close();
    magicNumber = (byte) ((size * size * size + size) / 2);

    long start = System.currentTimeMillis();
    solve(0, 0);
    printSquare();
    long duration = System.currentTimeMillis() - start;
    System.out.println(tmp);
    System.out.println(duration);
}

private boolean solve(int x, int y) {
    tmp++;
    if (x == square.length && y == square.length - 1 && isMagic()) {
        return true;
    }

    if (x == square.length) {
        y++;
        x = 0;
    }

    for (byte i = 1; i <= square.length * square.length; i++) {

        if (containsNumber(i) == false) { 

            if (isValidRow(x) && isValidCol(y)) {

                square[x][y] = i;

                if (solve(x + 1, y) == true) {
                    return true;
                }
            }

        }
    }

    if (x < square.length && y < square.length) {
        square[x][y] = 0;
    }

    return false;
}

private boolean isMagic() {

    int diagonal1 = 0;
    int diagonal2 = 0;
    int col = 0;
    int row = 0;

    for (int i = 0; i < square.length; i++) {

        for (int j = 0; j < square[0].length; j++) {

            col = col + square[j][i];
            row = row + square[i][j];

            if (i == 0) {
                diagonal1 = diagonal1 + square[j][j];
                diagonal2 = diagonal2 + square[j][square.length - j - 1];
            }

        }

        if (col != magicNumber || row != magicNumber || diagonal1 != magicNumber || diagonal2 != magicNumber) {
            return false;
        }

        row = 0;
        col = 0;
    }

    return true;
}

private boolean isValidRow(int row) {

    int sum = 0;

    for (byte i = 0; i < square.length; i++) {
        sum = sum + square[row][i];
    }

    if (sum <= magicNumber)
        return true;

    return false;
}

private boolean isValidCol(int col) {

    int sum = 0;

    for (byte i = 0; i < square.length; i++) {
        sum = sum + square[i][col];
    }

    if (sum <= magicNumber)
        return true;

    return false;
}

public boolean containsNumber(byte value) {

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

            if (square[i][j] == value) {
                return true;
            }

        }
    }
    return false;
}

private void printSquare() {

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

            System.out.print(square[i][j] + " ");

        }
        System.out.println();
    }
}

public static void main(String[] args) {

     MagicSquare m = new MagicSquare(); 

   }
}

Any help is really appreciated.

Answer 1

You should use try-with-resources when you create a Scanner, and should only ever open a Scanner on System.in in your main program. If you do this, you can pass the required size as an argument to the MagicSquare constructor:

public static void main(String[] args) {
    try(Scanner sc = new Scanner(System.in)) {
        byte size = sc.nextByte();
        MagicSquare m = new MagicSquare(size);
        m.printSquare();
    }
}

I’ve left construction of the magic square in the constructor (seems appropriate), but moved printing of the square to the main program. After all, you might not always want to print the magic square.

---

You have numerous inefficiencies in your implementation:

You use square.length and (worse!) square[0].length when you could simply use size if you stored the magic square’s size as a size member.

You are testing x < square.length && y < square.length before resetting square[x][y] = 0;. The x and y values should always be valid if you reach this step of the solve() method. But there is one small possibility of them becoming invalid. After filling in the last square...:

if (x == square.length && y == square.length-1 && isMagic()) {
    return true;
}

If it turns out isMagic() returns false, the method continues, loops over all values looking for an unused one (there aren’t any), and exits the method, returning false, but only after resetting square[x][y] = 0; which is why the check for invalid coordinates is required. If instead you used:

if (x == square.length && y == square.length-1) {
    return isMagic();
}

... then the method always returns immediately, whether or not the completely filled in square is magic or not. Now, the if guarding square[x][y] = 0; becomes unnecessary.

---

But the real issue comes from your algorithm as a whole. You loop over \$N^2\$ squares, and for each square try each of the \$N^2\$ values, and for each value check each of the \$N^2\$ squares to see if the value is already used. This is an \$O(N^6)\$ algorithm!

The usage check can be reduced to \$O(1)\$ by storing a “used” flag for each number:

boolean used[] = new boolean[size*size+1];

or

BitSet used = new BitSet(size*size + 1);

Then, simply checking used[value] or used.get(value) will return whether the value has been used or not. Set the flag for the value when you store it in the square[][], and clear it when you replace the value. That one change will reduce your time complexity from \$O(N^6)\$ to \$O(N^4)\$.

---

The next speed up can come from the observation that, if you take a solved NxN magic square, and erased one row and one column, you could trivially recreate the erased values. If you know N-1 values in a row or column, the remaining value must be the desired total less the sum of the filled in values. 1 + 8 + ? = 15 ... the missing value is 15-(1+8)=6! Of course, since you are generating candidate values, you need to ensure the computed value is (a) possible, and (b) unused.

---

Adding up numbers takes time. Why keep adding the values? You could keep a running total for each row and column:

square[x][y] = value;
row_sum[x] += value;
col_sum[y] += value;

... of course, you need to subtract the value out when backtracking, or replacing with a different candidate value.

---

Magic Squares are horizontally, vertically, and rotationally symmetric. In a 4x4 magic square, there are only 3 unique locations the number “1” may appear in. The remaining 13 locations would all correspond to simple rotations or mirroring of the square. This would reduce the possible 4x4 squares from 16! permutations down to 3*15! ... an 81% reduction. However, you are not finding all permutations; you stop once the first magic square is found, so this reduction in search space likely won’t produce much savings, if any.

---

While an 8x8 magic square seems huge, it is still within the realm of possibility. The magicNumber, however, would be 260 which is too large for a byte. Limiting the values themselves to a byte restricts the square to 15x15, and may be reasonable, but the sum should probably be an int.

---

This code ordering seems reversed!

    if (isValidRow(x) && isValidCol(y)) {
            square[x][y] = i;

square[x][y] should be filled in before the isValid checks are done. Otherwise, an invalid state will prevent updating the square to a valid value.

“Invalid”, in this case, only happens if the sum becomes too large, and subsequent values will only make matters worse, but if the code is relying on that, it should break out of the candidate values loop once an invalid state is reached, instead of continuing with the next value.