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

私はあなたがsolveメソッドからsolvePreviousを呼び出す必要はありませんだと思います。

私は、メソッドの名前について少し混乱しています。「前の」は、「前のセル」または「同じセルの前の番号」を意味する可能性があります。これはあなたが改善できるものです。

基本的な考え方は次のようになります。

/* 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); 
} 

この方法は、あなただけの「前方検索」。 2つのメソッドはお互いを再帰的に呼び出すため、すべての「前の」ステップはコール階層によって暗黙的に記憶されます。

でも、最初の空のボードでは、あなたのプログラムはlooooooong loooooongの時間を実行します。これは、最初の行の各フィールドの各番号（9^9 = 387420489）を試行するためです。 2番目の行に同様に多くのポジションがあると仮定すると、試行回数は150094635296999121に増えます。これは、発音の仕方がわからないほど大きい数字です。そして、それはちょうど2の行2です。

だから私は完全に異なるアプローチをとることをお勧めします：あなたが数字を入力するとすぐに、その行は、それぞれの行、列とボックスで禁じられているとマークします。そうすれば、毎回すべての行、列、ボックスをループする必要はありません。私が数独ソルバーをプログラムしたとき、私は数字がまだ可能な各セルを覚えておき、可能な限りそれらを排除して、繰り返し実行してすべての可能な数字を試してもうまくいった。