Sudoku

add better solutions here

Valid Sudoku, 检测每一行有里非'.'的字符里，有没有出现duplicate；检测每一列非'.'的的字符，有没有出现duplicate；检测每一个九宫格里（共9个），有没有出现非'.'的duplcate。

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0] == null || board[0].length != 9) {
            return false;
        }

        boolean[] visited = new boolean[9];
        for (int i = 0; i < 9; i++) {
            Arrays.fill(visited, false);
            for (int j = 0; j < 9; j++) {
                if (!isValid(board, i, j, visited)) {
                    return false;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            Arrays.fill(visited, false);
            for (int j = 0; j < 9; j++) {
                if (!isValid(board, j, i, visited)) {
                    return false;
                }
            }
        }

        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                Arrays.fill(visited, false);
                for (int k = 0; k < 9; k++) {
                    if (!isValid(board, i + k / 3, j + k % 3, visited)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

    private boolean isValid(char[][] board, int i, int j, boolean[] visited) {
        if (board[i][j] == '.') {
            return true;
        }

        int num = board[i][j] - '0';
        if (num < 1 || num > 9) {
            return false;
        }

        if (visited[num - 1]) {
            return false;
        }

        visited[num - 1] = true;
        return true;
    }
}

Sudoku Solver， 对于每一个character是’.'的字符，每次替换进一个‘valaid’字数，然后dfs下一层，直到找到solution为止。

public class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }

    private boolean dfs(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    continue;
                }

                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (dfs(board)) {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }

        return true;
    }

    private boolean isValid(char[][] board, int i, int j, char c) {
        for (int m = 0; m < 9; m++) {
            if (board[i][m] == c) {
                return false;
            }
        }

        for (int n = 0; n < 9; n++) {
            if (board[n][j] == c) {
                return false;
            }
        }

        int start_row = i / 3 * 3;
        int start_col = j / 3 * 3;

        for (int l = 0; l < 9; l++) {
            if (board[start_row + l / 3][start_col + l % 3] == c) {
                return false;
            }
        }

        return true;
    }
}