1

与えられたエッジの長さ（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);
}

}

4

1 に答える 1

2

他の配列を導入して、行、列、および2つの対角線の合計を追跡することができます。正方形に新しい数字を配置するか、正方形から数字を削除するたびに、これらの合計を更新する必要があります。次元が奇数の場合に注意してください。中央からの数値は両方の対角線に属しているため、両方の対角線の合計を更新する必要があります。

4つのケースがあります：

  1. 行がほぼいっぱいになっています（たとえば、次元が3で、最初の行にすでに2つの数値があります。次に、3番目の数値を推測する必要はなく、最初の数値の合計を引くことで取得できます。魔法の合計からの行、そしてそれが与えられている、それは次元にのみ依存します）
  2. （特定のケース）最後の行がほぼ満杯で、最後の列がほぼ満杯で、最初の対角線がほぼ満杯です（最初の列は左上の要素で始まり、右下の要素で終わる列です）。これは基本的に魔方陣の最後の位置です。
  3. ほぼ満杯のコラムがあります
  4. （特定のケース）最初の列がほぼいっぱいになっているため、2番目の列もほぼいっぱいになっています（右上の要素で始まり、左下の要素で終わる列としての2番目の列）
  5. （+1）通常の場合

これらの各ケースでは、欠落している数を推測する必要がないため、バックトラックを削減できます。これにより、必要な時間を短縮できます。

また、要素を対角線に挿入し、その後に他の位置に挿入すると、ほとんどのエラーが対角線で発生するため、余分な時間がかかります。そして、本当に高速にしたい場合は、C /C++でコードを書くことを検討してください。

于 2014-03-01T12:40:24.467 に答える