bool solveSudoku(vector< vector<char> >& board) {
    for (int i=0; i<9; ++i){
        for (int j=0; j<9; ++j){
            if (board[i][j]=='.'){
                for (int k=0; k<9; ++k){
                    board[i][j]=('1'+k);
                    if (check(i,j, board)){
                        if (solveSudoku(board)){
                            return true;
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}
bool check(int i, int j, vector< vector<char> >& board){
    //check horizontal
    for (int l=0; l<9; ++l){
        if (board[i][l]==board[i][j] && l!=j){
            return false;
        }
    }
    //check vertical
    for (int l=0; l<9; ++l){
        if (board[l][j]==board[i][j] && l!=i){
            return false;
        }
    }
    //check block
    int block_x = i/3;
    int block_y = j/3;
    block_x*=3;
    block_y*=3;
    for(int l=0; l<3; ++l){
        for (int k=0; k<3; ++k){
            if (board[block_x+l][block_y+k]==board[i][j] && block_x+l!=i && block_y+k!=j){
                return false;
            }
        }
    }
    //all valid so return true
    return true;
}