java - Sudoku Solver的代码说明

我对以下代码段有疑问:
它是一种数独解算器，它通过填充空单元格来解决数独难题。
我不能真正获得求解器方法背后的逻辑。为什么在尝试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;
}
}

最佳答案

每个递归调用都会处理第一个“。”。还有待处理。暂时将替换为数字。如果更改成功(不会使评估板无效)，请进行递归操作(将尝试下一个“。”)。如果那将失败，请撤消本地所做的更改并返回false，因为在此搜索分支上尝试的任何数字均无效。这意味着强制调用者(最大权限)尝试下一个选择。

关于java - Sudoku Solver的代码说明，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15182546/