需要帮助进行优化 - 在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++编写代码。