/*
http://www.csie.ntnu.edu.tw/~u91029/Backtracking.html#1
回溯法&&DFS==【退回，已经操作的状态复原】
所有解void
void sovle(char[][] board, int x, int y) {
    if(y == 9) {y = 0; x++;}
    if(x == 9) {solution(); return;}
    //do thing
}
有一解boolean
boolean sovle(char[][] board)
boolean sovle(cahr[][] board,int x,int y)
*/
public class Solution {
    public void solveSudoku(char[][] board) {
        sovle(board);
    }
    
 private boolean sovle(char[][] board) {  
        for(int i = 0;i<9;i++)  
            for(int j = 0;j<9;j++) {  
                if(board[i][j] == '.') {  
                    for(char k = '1';k<='9';k++) {  
                        board[i][j] = k;  
                        if(isVaild(board,i,j) && sovle(board)) {  
                            return true;  
                        }  
                    }  
                    board[i][j] = '.';  
                    return false;  
                }  
            }  
        return true;  
    }  
    
    private boolean isVaild(char[][] board,int i,int j) {
        int[] row = new int[9];
        int[] column = new int[9];
        int[] block = new int[9];
        int a = i/3*3;
        int b = j/3*3;
        for(int k = 0;k<9;k++) {
            if(board[i][k] != '.') {
                if(row[board[i][k]-'1']>0) return false;
                else {
                    row[board[i][k]-'1']++;
                }
            }
            if(board[k][j] != '.') {
                if(column[board[k][j]-'1']>0) return false;
                else {
                    column[board[k][j]-'1']++;
                }
            }
        }
        for(int k1 = 0;k1<3;k1++)
            for(int k2 = 0;k2<3;k2++) {
                if(board[a+k1][b+k2] != '.') {
                    if(block[board[a+k1][b+k2]-'1']>0) return false;
                    else {
                        block[board[a+k1][b+k2]-'1']++;
                    }
                }
            }
        return true;
    }
}