Нужна помощь для оптимизации - создание магических квадратов в Java

Question

Я должен реализовать алгоритм, который создает все возможные магические квадраты для данной длины ребра (n=3,4). При n = 3 алгоритм работает нормально. Но для n=4 алгоритм не дает никаких результатов, потому что он не оптимален (слишком медленный). Я попытался оптимизировать алгоритм, но он все еще не работает, как следует. Любая помощь с благодарностью.

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

Вы можете ввести другие массивы для отслеживания сумм в строках, столбцах и на 2 диагонали. Вам необходимо обновлять эти суммы всякий раз, когда вы помещаете новое число в квадрат или удаляете число из него. Обратите внимание на случай, когда у вас есть нечетное измерение, число от середины принадлежит обеим диагоналям, поэтому обе диагональные суммы необходимо обновить.

У вас есть 4 случая:

1. у вас есть почти полная строка (например, размерность равна 3, и у вас уже есть 2 числа в первой строке, например. Тогда вам не нужно угадывать третье число, вы можете получить его, вычитая сумму первого ряд от магической суммы, и то, что дано, зависит только от размерности)
2. (в конкретном случае) последняя строка почти заполнена, последний столбец почти заполнен, а первая диагональ почти заполнена (первый столбец - это столбец, который начинается с верхнего левого элемента и заканчивается нижним правым элементом). Это в основном последняя позиция в магическом квадрате.
3. у вас почти полная колонка
4. (в конкретном случае) первый столбец почти заполнен, и, таким образом, второй столбец также почти заполнен (второй столбец - это столбец, который начинается с правого верхнего элемента и заканчивается левым нижним элементом)
5. (+1) обычный случай

В каждом из этих случаев вы можете сократить возврат, потому что вам не нужно угадывать пропущенное число. Это может сократить необходимое время.

Кроме того, если вы вставите элементы в диагонали, и только после этого в других позициях, это даст вам дополнительное время, так как большинство ошибок происходит на диагонали. И если вы хотите очень-очень быстро, подумайте о написании кода на C/C++.