Need help for optimization - generating magic squares in java

Question

I have to implement an algorithm which creates all possible magic squares for a given edge length(n=3,4). For n=3 the algorithm works fine. But for n=4 the algorithm don't get any results, because it's not optimal(too slow). I tried to optimize the algorithm but it is still not working as it should. Any help is greatly appreciated.

public class MagicSquare {

private int[][] square;
private boolean[] possible;
private int totalSqs;
private int sum;
private static int numsquares;


public MagicSquare(int n){
    square = new int[n][n];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            square[i][j] = 0;
        }
    }

    totalSqs = n*n;
    possible = new boolean[totalSqs];
    for(int i=0; i<totalSqs; i++)
        possible[i] = true;

    sum = n*(n*n+1)/2;
    numsquares = 0;
    fill(0, 0);
}

public void fill(int row, int col){
    for(int i=0; i<totalSqs; i++){
        if(possible[i]){
            square[row][col] = i+1;
            possible[i] = false;

            int newcol = col+1;
            int newrow = row;
            if(newcol == square.length){
                newrow++;
                newcol = 0;
            }

            fill(newrow,newcol);
            square[row][col] = 0;
            possible[i] = true;
        }
    }

    if(!checkRows() || !checkCols())
        return;

    if(row == square.length){
        for(int i=0; i<square.length; i++ ){
            for(int j=0; j<square[i].length; j++){
                System.out.print(square[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
        numsquares++;
        return;
    }
}

public boolean checkRows(){
    for(int i=0; i<square.length; i++){
        int test = 0;
        boolean unFilled = false;

        for(int j=0; j<square[i].length; j++){
            test += square[i][j];
            if(square[i][j] == 0)
                unFilled = true;
        }

        if(!unFilled && test!=sum)
            return false;
    }
    return true;
}

public boolean checkCols(){
    for(int j=0; j<square.length; j++){
        int test = 0;
        boolean unFilled = false;

        for(int i=0; i<square[j].length; i++){
            test += square[i][j];
            if(square[i][j] == 0)
                unFilled = true;
        }

        if(!unFilled && test!=sum)
            return false;
    }
    return true;
}

public static void main(String[] args) {
    new MagicSquare(3);
    System.out.println(numsquares);
}

}

Answer 1

You could introduce other arrays to keep track of the sums in rows, columns and on the 2 diagonals. You need to update these sums whenever you place a new number in the square or remove a number from it. Pay attention to the case when you have an odd dimension, the number from the middle belongs to both diagonals, so both of the diagonal sums need to be updated.

You have 4 cases:

1. you have a row almost full (e.g. the dimension is 3, and you have already 2 numbers in the first row, for instance. Then you needn't have to guess the third number, you can have it by subtracting the sum of the first row from the magic sum, and that is given, it depends only on the dimension)
2. (specific case) you have the last row almost full, the last column almost full, and the first diagonal almost full (first column as the column that starts with the top left element and ends with the bottom right element). This is basically the last position in the magic square.
3. you have a column almost full
4. (specific case) you have the first column almost full, and thereby you also have the second column almost full (second column as the column that starts with the top right element and ends with the bottom left element)
5. (+1) ordinary case

In each of these cases you can cut the backtracking, because you don't have to guess the missing number. This can reduce the time needed.

Also, if you insert the elements on the diagonals, and only after that on the other positions, this will buy you extra time, as the most errors occur on the diagonals. And if you want it really-really fast, consider writing the code in C/C++.