37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character'.'.

You may assume that there will be only one unique solution.

Analysis

link: https://leetcode.com/problems/sudoku-solver/discuss/15752/Straight-Forward-Java-Solution-Using-Backtracking

Solution from Forum

public void solveSudoku(char[][] board) {
    doSolve(board, 0, 0);
}

private boolean doSolve(char[][] board, int row, int col) {
    for (int i = row; i < 9; i++, col = 0) { // note: must reset col here!
        for (int j = col; j < 9; j++) {
            if (board[i][j] != '.') continue;
            for (char num = '1'; num <= '9'; num++) {
                if (isValid(board, i, j, num)) {
                    board[i][j] = num;
                    if (doSolve(board, i, j + 1))
                        return true;
                    board[i][j] = '.';
                }
            }
            return false;
        }
    }
    return true;
}

private boolean isValid(char[][] board, int row, int col, char num) {
    int blkrow = (row / 3) * 3, blkcol = (col / 3) * 3; // Block no. is i/3, first element is i/3*3
    for (int i = 0; i < 9; i++)
        if (board[i][col] == num || board[row][i] == num || 
                board[blkrow + i / 3][blkcol + i % 3] == num)
            return false;
    return true;
}