최적화를위한 도움이 필요합니다 - 자바에서 마술 사각형 생성

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 대각선의 합계를 추적하기 위해 다른 배열을 소개 할 수있다. 사각형에 새 번호를 입력하거나 번호를 제거 할 때마다이 합계를 업데이트해야합니다. 홀수 디멘션이있는 경우에는 중간에있는 숫자가 대각선에 속하므로 대각선 합계를 모두 업데이트해야합니다.

당신은 사가지 경우가 있습니다

1. 거의 가득 행이 (예 : 치수는 3, 당신은 예를 들어 그런 다음 당신이 필요가 없습니다, 첫 번째 행에서 이미이 개 숫자를 가지고있다. 세 번째 숫자를 추측하기 위해서는 첫 번째 행의 합계를 빼서 마술 합계에서 빼고 그 값을 차원에 따라 달라야합니다.
2. (특정 경우) 마지막 행은 거의 꽉 찼습니다 ()., 마지막 열 거의 거의 및 첫 번째 대각선 거의 전체 (첫 번째 열은 왼쪽 상단 요소에서 시작하여 오른쪽 하단 요소로 끝나는 열입니다). 이것은 기본적으로 마술 광장의 마지막 위치입니다.
3. 은 거의 전체 열이
4. (특정한 경우)는 거의 전체 첫 번째 열을 가지며, 이에는 또한 시작 열 거의 전체 (제 컬럼 번째 열이 오른쪽 상단 요소와 왼쪽 아래 요소로 끝)
5. (+1) 보통의 경우 당신이 누락 된 숫자를 추측 할 필요가 없기 때문에 당신의 역행을 줄일 수 이러한 각각의 경우에

. 이렇게하면 필요한 시간을 줄일 수 있습니다.

또한 대각선에 요소를 삽입 한 후에 다른 요소에 요소를 삽입하면 대각선에서 가장 많은 오류가 발생하므로 추가 시간이 소요됩니다. 그리고 정말로 빠르게 수행하기를 원한다면 C/C++로 코드를 작성하는 것을 고려해보십시오.