java - Sudoku Solver的代码解释

Question

我对以下代码片段有疑问: 它是一个数独求解器，通过填充空单元格来解决数独难题。 我无法真正理解求解器方法背后的逻辑。为什么它在尝试 k=1-9 后返回 false 并在遍历所有单元格后返回 true 。我的想法是我们递归地进入 solver() 方法，一旦数独完成，它将返回 true 作为调用顺序，最后第一个调用的 solver() 将返回 true。我想我必须省略一些发生上述两个“返回”的场景。有人可以向我解释为什么这些“返回”应该存在吗？

public class Solution {

public static void main(String[] args) {
    Solution s = new Solution();
    char[][] board = {{'.', '2', '6', '5', '.', '.', '.', '9', '.'},
                      {'5', '.', '.', '.', '7', '9', '.', '.', '4'},
                      {'3', '.', '.', '.', '1', '.', '.', '.', '.'},
                      {'6', '.', '.', '.', '.', '.', '8', '.', '7'},
                      {'.', '7', '5', '.', '2', '.', '.', '1', '.'},
                      {'.', '1', '.', '.', '.', '.', '4', '.', '.'},
                      {'.', '.', '.', '3', '.', '8', '9', '.', '2'},
                      {'7', '.', '.', '.', '6', '.', '.', '4', '.'},
                      {'.', '3', '.', '2', '.', '.', '1', '.', '.'}};

    s.solver(board);
}
public boolean solver(char[][] board) {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (board[r][c] == '.') {
                for (int k = 1; k <= 9; k++) {
                    board[r][c] = (char) ('0' + k);
                    if (isValid(board, r, c) && solver(board)) {
                        return true;
                    } else {
                        board[r][c] = '.';
                    }
                 }
                return false;
             }
         }
     }
    return true;
}

public boolean isValid(char[][] board, int r, int c) {
    //check row
    boolean[] row = new boolean[9];
    for (int i = 0; i < 9; i++) {
        if (board[r][i] >= '1' && board[r][i] <= '9') {
            if (row[board[r][i] - '1'] == false) {
                row[board[r][i] - '1'] = true;
            } else {
                return false;
            }
        }
    }

    //check column
    boolean[] col = new boolean[9];
    for (int i = 0; i < 9; i++) {
        if (board[i][c] >= '1' && board[i][c] <= '9') {
            if (col[board[i][c] - '1'] == false) {
                col[board[i][c] - '1'] = true;
            } else {
                return false;
            }
        }
    }

    //check the 3*3 grid
    boolean[] grid = new boolean[9];
    for (int i = (r / 3) * 3; i < (r / 3) * 3 + 3; i++) {
        for (int j = (c / 3) * 3; j < (c / 3) * 3 + 3; j++) {
            if (board[i][j] >= '1' && board[i][j] <= '9') {
                if (grid[board[i][j] - '1'] == false) {
                    grid[board[i][j] - '1'] = true;
                } else {
                    return false;
                }
            }
         }
    }

    return true;
}
}

Answer 1

每个递归调用都会处理第一个 '.'还是要处理的。这将暂时用一个数字代替。如果更改成功(不会使电路板无效)，请递归(将尝试下一个“.”)。如果失败，撤消本地所做的更改并返回 false，因为在此搜索分支上尝试的任何数字都是无效的。这意味着强制调用者(直到 root)尝试下一个选择。