Code explanation of Sudoku Solver

Question

I have question about the following code snippet: It is a sudoku solver which solves a Sudoku puzzle by filling the empty cells. I can not really get the logic behind the solver method. Why does it return false after trying k=1-9 and return true after looping over all cells. What I thought is we recursively get into solver() method and once the sudoku is done, it will return true back as invoking order and finally the first invoked solver() will return true. I think I must omit some scenarios that above two "return" happen. Could someone explain to me why should those "return" exist?

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

Each recursive call take care of the first '.' still to be handled. That will be replaced tentatively with a digit. If the change is successful (does not invalidate the board) go recurse (will try next '.'). If that will fail undo the change done locally and return false, because any digit tried on this search branch is invalid. This means to force the caller (up to root) to try the next choice.

Answer 2

This is a simple brute force solver. It just tries every number in every open space. If the board is 'valid' (follows the rules of the game) after filling in a given space with a number, then it recursively calls the same solver function which fill in another blank spot and test if that the board is still valid and so on.

It is a highly inefficient solver, but easy to code.