需要幫助進行優化 - 在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++編寫代碼。