37. Sudoku Solver

backtracking

/*

    time complexity: O(9^m), m represents the number of blanks to be filled in
    space complexity: O(1)

*/
class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {

                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) { //每個位置一一放入去try
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c; //set value

                            if (solve(board)) return true; // resursive, find unique solution, ealry stop

                            board[i][j] = '.'; // backtrack
                        }

                    }
                    return false;
                }
            }
        }
        return true;
    }

    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) { //判斷9個格子
            char rowVal = board[row][i];
            if (rowVal != '.' && rowVal == c) return false;

            char colVal = board[i][col];
            if (colVal != '.' && colVal == c) return false;

            // 因為沒有用set, 所以判斷式是這樣, 這裡再針對(i,j) 去判斷9宮格內是否有c了
            char boxVal = board[3*(row/3) + i/3][3*(col/3) + i%3];
            if (boxVal != '.' && boxVal == c) return false;
        }
        return true;
    }
}

T: O(9!^9), 每列有 9! 的放入可能, 9 列, 所以是 O(9!^9)

S: O(9*9) = O(81)

更好懂的寫法

class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }
    private boolean dfs(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                
                if (board[i][j] != '.') { // not empty, pass, do dfs from '.'
                    continue;
                }
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) { // validate
                        board[i][j] = c; // try '1' to '9'
                        
                        if (dfs(board)) { // dfs
                            return true;
                        }
                        
                        board[i][j] = '.'; // backtracking
                    }
                }
                return false;
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] != '.' && board[row][i] == c) {
                return false;
            }
            if (board[i][col] != '.' && board[i][col] == c) {
                return false;
            }
        }
        
        int startRow = 3*(row/3);
        int startCol = 3*(col/3);
        for (int i = startRow; i < startRow+3; i++) {
            for (int j = startCol; j < startCol+3; j++) {
                if (board[i][j] != '.' && board[i][j] == c) {
                    return false;
                }
            }
        }
        return true;
    }
}

/*
最後用 startRow, startCol 來推 box 內 9 個座標
取的某點, ex 45, 3*(4/3), 3*(5/3) 取得起始座標=> 3,3

33.  3,4  35
43.  44.  45
53.  54.  55  => startRow, startCol = 3,3
ex 45, 3*(4/3), 3*(5/3) => 3,3

*/

```java
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board, 0, 0);
    }
    private boolean dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        if (i == m) {
            return true;
        }
        if (j == n) { //col j reach n, so do next row, and col = 0
            return dfs(board, i+1, 0);
        }
        if (board[i][j] != '.') {
            return dfs(board, i, j+1);
        }
        for (char c = '1'; c <= '9'; c++) { // try to put each char into it
            if (isValid(board, i, j, c)) {
                board[i][j] = c;
                if (dfs(board, i, j+1)) {
                    return true;
                }
                board[i][j] = '.';
            }
        }
        return false;
    }
    private boolean isValid(char[][] board, int r, int c, char newChar) {
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == newChar) {
                return false;
            }
            if (board[i][c] == newChar) {
                return false;
            }
        }
        int startR = r/3*3;
        int startC = c/3*3;
        for (int i = startR; i < startR+3; i++) {
            for (int j = startC; j < startC+3; j++) {
                if (board[i][j] == newChar) {
                    return false;
                }
            }
        }
        return true;
    }
}

/*
how to check it is valid?

if (board[r][i] == n) return false;
        // 判断列是否存在重复
        if (board[i][c] == n) return false;
        // 判断 3 x 3 方框是否存在重复
        if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
            return false;


            3, 0

            3,0 4,0 5,0
            3,1.4,1 5,1  
            3,2 4,2.5,2



if j == n
dfs(i+1, 0)

not '.'
dfs(i, j+1)

if valid
dfs(i, j+1)

*/
```