37. Sudoku Solver

T: O(9^m), m is empty slot

S:O(1)

```java
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board, 0, 0);
    }
    private boolean dfs(char[][] board, int row, int col) {
        int n = board.length;
        if (row == n) {
            return true;
        }
        if (col == n) {
            return dfs(board, row+1, 0);
        }
        if (board[row][col] != '.') {
            return dfs(board, row, col+1);
        }

        for (char c = '1'; c <= '9'; c++) {
            if (isValid(board, row, col, c)) {
                board[row][col] = c;
                if (dfs(board, row, col+1)) {
                    return true;
                }
                board[row][col] = '.';
            }
        }
        return false;
    }
    private boolean isValid(char[][] board, int row, int col, char num) {
        int n = board.length;
        // check row
        for (int i = 0; i < n; i++) {
            if (board[row][i] == num) {
                return false;
            }
        }
        // check col
        for (int i = 0; i < n; i++) {
            if (board[i][col] == num) {
                return false;
            }
        }
        // check cell
        int baseRow = (row/3) * 3;
        int baseCol = (col/3) * 3;
        for (int r = baseRow; r < baseRow + 3; r++) {
            for (int c = baseCol; c < baseCol + 3; c++) {
                if (r != row && c != col) {
                    if (board[r][c] == num) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
/*

00 01 02
10 11 12x
20 21 22

03 04 05
13 14 15
23 24 25

row 44
4/3 = 1 , 
4/3 = 1
row/3 * 3
33 34 35
43 44 45
53 54 55
*/
```