我想制作一个数独求解器

Question

这是代码：

public class sudoku {
    public static void printSudoku(int sudoku[][]){
        for(int i = 0; i < sudoku.length; i++){
            for(int j = 0; j < sudoku[i].length; j++){
                System.out.print(sudoku[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void sudokuSolver(int sudoku[][], int i, int j){
        if (i == 8 && j == 8) {
            printSudoku(sudoku);
            return;
        }
        if (j == sudoku[i].length) {
            sudokuSolver(sudoku, i+1, 0);
        }
        for(int n = 1; n <= 9; n++){
            if (isSafe(sudoku, i, j, n)) {
                sudoku[i][j] = n;
            }
            sudokuSolver(sudoku, i, j+1);
        }
    }
    public static boolean isSafe(int sudoku[][], int i, int j, int n){
        //row
        for(int c = 0; c <= 8; c++){
            if (sudoku[i][c] == n) {
                return false;
            }
        }
        //col
        for(int r = 0; r <= 8; r++){
            if (sudoku[r][j] == n) {
                return false;
            }
        }

        //matrix
        int sr = (i/3)*3, sc = (j/3)*3;
        for(int r = sr; r<sr+3;r++){
            for(int c = sc; c < sc+3; c++){
                if (sudoku[r][c]==n) {
                    return false;
                }
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int sudoku[][] = {{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}};
        sudokuSolver(sudoku, 0, 0);
    }
}

我知道我们可以使用回溯来解决它。但是这个方法有什么问题，我不知道为什么堆栈会溢出，因为我也设置了基本情况。

我期待着一个解决的sudoky。相反，我收到“堆栈溢出错误”。

Answer 1

有几个问题：

• 当条件

  j == sudoku[i].length

  为真并且递归调用返回时，继续执行下面的

  for

  循环，其中

  j+1

  被传递给递归调用，现在永远不会达到基本情况，如下所示下一次递归调用将具有

  j

  的值，即无限期地增加一个值，直到遇到堆栈溢出。解决方案是在调用后立即添加

  return

  sudokuSolver(sudoku, i+1, 0)

• 在

  for

  循环中，递归调用是无条件进行的，当无法放置值时也是如此（

  isSafe

  返回

  false

  ）。但这意味着相应的单元格留空，最终基本情况将启动并打印一块大部分由零填充的板。相反，只有当值 could 放置在单元格中时才应进行递归调用 - 因此将其放置在

  if isSafe

  块内。否则，

  for

  循环应该尝试另一个值而不进行递归调用。

• 由于您不应用回溯，但从递归返回后继续do，因此您必须考虑到由更深层次的递归调用填充的单元格仍然存在，并且板只会获得更多值（永远不会更少），直到它表示无法填写更多有效单元格的配置。然后该过程将永远找不到有效的数独。最简单的解决方案是添加一行代码来实现回溯，即将当前单元格设置回 0。

这是您的代码，并对上述内容进行了更正。评论指出了更改的地方：

    public static void printSudoku(int sudoku[][]){
        for(int i = 0; i < sudoku.length; i++){
            for(int j = 0; j < sudoku[i].length; j++){
                System.out.print(sudoku[i][j] + " ");
            }
            System.out.println();
        }
        // For better visual distinction between different Sudokus, 
        //    leave one line empty in the output: 
        System.out.println(); 
    }

    public static void sudokuSolver(int sudoku[][], int i, int j){
        if (i == 8 && j == 8) {
            printSudoku(sudoku);
            return;
        }
        if (j == sudoku[i].length) {
            sudokuSolver(sudoku, i+1, 0);
            // Don't allow execution to continue into the loop below 
            //    with an invalid value for `j`:
            return; 
        }
        for(int n = 1; n <= 9; n++){
            if (isSafe(sudoku, i, j, n)) {
                sudoku[i][j] = n;
                // The recursive call should only be made when we placed a value
                sudokuSolver(sudoku, i, j+1);
                // We must backtrack to have any hope of success:
                sudoku[i][j] = 0;
            }
        }
    }