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 个数字。那么您不必猜测第三个数字，您可以通过减去第一个数字的总和来得到它来自幻数的行，这是给定的，它只取决于维度）
  2. （特定情况）您的最后一行几乎已满，最后一列几乎已满，第一个对角线几乎已满（第一列是从左上角元素开始并以右下角元素结束的列）。这基本上是幻方中的最后一个位置。
  3. 你有一列几乎满了
  4. （特定情况）您的第一列几乎已满，因此您的第二列也几乎已满（第二列是从右上角元素开始并以左下角元素结束的列）
  5. (+1) 普通情况

在每种情况下，您都可以减少回溯，因为您不必猜测丢失的数字。这可以减少所需的时间。

此外，如果您在对角线上插入元素，并且仅在其他位置插入元素，这将为您赢得额外的时间，因为大多数错误发生在对角线上。如果你想要它真的非常快，可以考虑用 C/C++ 编写代码。

于 2014-03-01T12:40:24.467 回答