Java遞歸數獨求解器中的堆棧溢出錯誤

Question

我對編碼通常很陌生，現在我正在用java寫一個遞歸數獨求解器。然而，我不斷收到堆棧溢出錯誤，我不能爲我的生活找出原因。

以下是整個代碼。據說錯誤在於各種解決方法。

import java.util.*; 
public class sudoku{ 

protected static int n; 
protected static int[][] game; 

public static boolean checkRow(int a, int b){ 
    boolean z = true; 
    for(int i=0;i<n;i++){ 
     if(i==b) continue; 
     else if(game[a][b]==game[a][i]){ 
      z = false; 
      break; 
     } 
    } 
    return(z); 
} 

public static boolean checkColumn(int a, int b){ 
    boolean z = true; 
    for(int i=0;i<n;i++){ 
     if(i==a) continue; 
     else if(game[i][b]==game[a][b]){ 
      z = false; 
      break; 
     } 
    } 
    return(z); 
} 

public static boolean checkBox(int a, int b){ 
    boolean z = true; 
    int x = (int)Math.sqrt(n)*(int)(a/Math.sqrt(n)); 
    int y = (int)Math.sqrt(n)*(int)(b/Math.sqrt(n)); 
     for(int i=x;i<x+Math.sqrt(n);i++){ 
      for(int j=y;j<y+Math.sqrt(n);j++){ 
       if(a==i&&b==j) continue; 
       else if(game[a][b]==game[i][j]){ 
        z = false; 
        break; 
       } 
      } 
     } 
    return(z); 
} 

public static boolean checkAll(int a, int b){ 
    return(checkRow(a,b)&&checkColumn(a,b)&&checkBox(a,b)); 
} 

public static void solvePrevious(int row, int col){ 
    if(row==0&&col==0){ 
     System.out.println("This game is unsolvable."); 
     return; 
    } 
    else if(col==0) solve(row-1,n-1,game[row-1][n-1]+1); 
    else solve(row,col-1,game[row][col]+1); 
} 

public static void solveNext(int row, int col){ 
    if(row==n-1&&col==n-1) return; 
    else if(col==n-1) solve(row+1,0,1); 
    else solve(row,col+1,1); 
} 

public static void solve(int row, int col, int value){ 
    if(value<=n){ 
     game[row][col] = value; 
     if(checkAll(row,col)) solveNext(row,col); 
     else solve(row,col,value+1); 
    } 
    else solvePrevious(row,col); 
} 

public static void main(String[] args){ 
    Scanner inp = new Scanner(System.in); 
    System.out.println("What is the side length of the puzzle?"); 
    n = 0; 
    do{ 
     n = inp.nextInt(); 
     if(Math.sqrt(n)%1!=0) System.out.println("The side length must be a perfect square."); 
    }while(Math.sqrt(n)%1!=0); 
    game = new int[n][n]; 
    solve(0,0,1); 
    for(int i=0;i<n;i++){ 
     for(int j=0;j<n;j++){ 
      System.out.print(game[i][j]+" "); 
     } 
     System.out.println(" "); 
    } 
} 

}

Answer 1

我覺得你不需要調用solvePrevious從solve方法。

我對方法名稱有點困惑 - 「上一個」可能意味着「先前的單元格」或「同一單元格的前一個數字」。這是你可以改進的地方。

的基本思路應該是這樣的：

/* in main: */ 
solve(0, 0, 1); 

solve(row, col, num) { 
    if (checkAll(row, col)) { 
    solveNextCell(row, col); 
    } 
    if (num < n * n) { 
    solve(row, col, num + 1); 
    } 
} 

solveNextCell(row, col) { 
    if (row == n - 1 && col == n - 1) 
    printSolution(); 
    else if (col == n - 1) 
    solve(row + 1, 0, 1); 
    else 
    solve(row, col + 1, 1); 
} 

這樣，你只有「向前搜索」。因爲這兩個方法遞歸地相互調用，所有「以前的」步驟都會被調用層次隱式地記住。

但即使如此，您的程序仍然會運行一段時間，至少對於最初是空的板來說。這是因爲它會嘗試第一行的每個字段中的每個數字，它們是9^9 = 387420489。假設在第二排有類似的許多職位，嘗試的數量增長到150094635296999121，這是一個很大的數字，我不知道如何發音。這就是第9行第2行。

所以我建議你採取一種完全不同的方法：只要你填寫一個數字，你就將該數字標記爲在相應的行，列和框中禁止。這樣，您不必循環遍歷所有行，列和框。當我編程一個Sudoku求解器時，我記得每個單元格的數字仍然可行，並且儘可能排除它們，甚至在開始遞歸併嘗試每個可能的數字之前，我都取得了很好的成功。