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.

A sudoku puzzle...

...and its solution numbers marked in red.

一刷
題解：
DFS+backtracking

public class Solution {
    public void solveSudoku(char[][] board) {
        canSolveSudoku(board);
    }
    
    private boolean canSolveSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return false;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                    if (isCurrentBoardValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (canSolveSudoku(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';       // backtracking
                            }
                        }
                    }
                    return false;    
                }
            }
        }
        return true;
    }
    
    private boolean isCurrentBoardValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == c) {
                return false;
            }
        }
        
        for (int j = 0; j < board[0].length; j++) {
            if (board[row][j] == c) {
                return false;
            }
        }
        
        for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
            for (int j = col / 3 * 3; j < col /3 * 3 + 3; j++) {
                if (board[i][j] == c) {
                    return false;
                }
            }
        }
        return true;
    }
}

二刷：
DFS + BackTracking

public class Solution {
    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0) return;
        solve(board);
    }
    
    public 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++){
                       if(isValid(board, i, j, c)){
                            board[i][j] = c;
                       
                            if(solve(board)) return true;
                            else board[i][j] = '.';
                       }
                   }
                   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] == c || board[i][col] == c) return false;
           if(board[row/3 * 3 + i/3][col/3*3 + i%3] == c) return false;
       }
        return true;
    }
}