Stack Overflow Fehler in Java Rekursive Sudoku Solver

Question

Ich bin ziemlich neu zu Codierung im Allgemeinen und ich schreibe einen rekursiven Sudoku-Löser jetzt in Java. Allerdings bekomme ich immer einen Stack Overflow Fehler und ich kann nicht für das Leben von mir herausfinden, warum.

Hier ist der ganze Code. Der Fehler liegt angeblich in den verschiedenen Lösungsmethoden.

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

Ich glaube, Sie müssen solvePrevious nicht Anruf aus der solve Methode.

Ich bin ein wenig verwirrt über die Methodennamen - die "vorherige" könnte entweder "vorherige Zelle" oder "vorherige Nummer für die gleiche Zelle" bedeuten. Das könntest du verbessern.

Die Grundidee sollte wie folgt aussehen:

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

diese Weise „suchen vorwärts“ Sie. Da sich die beiden Methoden rekursiv aufrufen, werden alle "vorherigen" Schritte implizit von der Aufrufhierarchie gespeichert.

Aber auch dann wird Ihr Programm eine laaaaaaaaange laaaaaaaaaaaaaaaaegige Zeit laufen, zumindest für die anfänglich leere Platine. Dies ist, weil es jede Zahl in jedem Feld der ersten Zeile versucht, die 9^9 = 387420489 sind. Nimmt man an, dass es in der zweiten Zeile ähnlich viele Positionen gibt, wächst die Anzahl der Versuche auf 150094635296999121, was eine so große Zahl ist, dass ich nicht weiß, wie ich sie aussprechen soll. Und das ist nur Zeile 2 von 9.

Also schlage ich vor, dass Sie einen ganz anderen Ansatz nehmen: Sobald Sie eine Zahl eingeben, markieren Sie diese Nummer als verboten in der jeweiligen Zeile, Spalte und Box. Auf diese Weise müssen Sie nicht jedes Mal alle Zeilen, Spalten und Boxen durchlaufen. Als ich einen Sudoku-Solver programmierte, hatte ich großen Erfolg darin, sich für jede Zelle zu merken, welche Zahlen noch möglich sind, und sie so weit wie möglich auszuschließen, bevor ich überhaupt anfing, jede mögliche Zahl zu rekrutieren und auszuprobieren.