java - java递归数独求解器中的堆栈溢出错误

Question

我对一般编码还很陌生，我现在正在用 java 编写一个递归数独求解器。然而，我不断收到 Stack Overflow 错误，而且我一辈子都无法找出原因。

这是完整的代码。据推测，错误在于各种求解方法。

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

这样，您只需“向前搜索”。由于这两个方法递归地相互调用，因此调用层次结构会隐式记住所有“先前”步骤。

但即便如此，你的程序也会运行很长很长的时间，至少对于最初的空板来说是这样。这是因为它会尝试第一行每个字段中的每个数字，即 9^9 = 387420489。假设第二行也有同样多的位置，尝试的次数就会增加到150094635296999121，这个数字太大了，我不知道如何发音。这只是 9 行中的第 2 行。

所以我建议你采取完全不同的方法:一旦你填写了一个数字，你就在相应的行、列和框中将该数字标记为禁止。这样，您就不必每次都循环遍历所有行、列和框。当我编写数独解算器时，我成功地记住了每个单元格中哪些数字仍然是可能的，并在开始递归和尝试每个可能的数字之前尽可能排除它们。