Sudoku Solver

three flavors are provided.

//first flavor
class Solution {
public:
    typedef vector<vector<char> > BOARDTYPE;
   
    void solveSudoku(BOARDTYPE &board) {
        solveSudokuRe(board, 0, 0);
    }
   
    bool solveSudokuRe(BOARDTYPE &board, int row, int col) {
        if(col>=9)
            return solveSudokuRe(board,row+1,0);
        if(row==9)
            return true;
        if(board[row][col]=='.'){
            for(int i=0;i<9;i++){
                board[row][col]='1'+i;
                if(isValid(board,row,col))
                    if(solveSudokuRe(board,row,col+1))
                        return true;
                board[row][col]='.';       
            }
           
        }
        else{
            return solveSudokuRe(board,row,col+1);
        }
        return false;
       
    }
    bool isValid(BOARDTYPE &board, int row, int col){
        for(int k=0;k<9;k++){
            if((k!=row&&board[k][col]==board[row][col])||(k!=col&&board[row][k]==board[row][col]))
                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(!(i==row&&j==col)&&board[i][j]==board[row][col])
                    return false;
        return true;           
    }
    //another flavor of isValid function
    bool isValid2(BOARDTYPE &board, int row, int col){
        for(int k=0;k<9;k++){
             if((k!=row&&board[k][col]==board[row][col])||(k!=col&&board[row][k]==board[row][col]))
                return false;
        }
        for(int k=0;k<9;k++){
            int i=row/3*3+k/3;
            int j=col/3*3+k%3;
            if(!(i==row&&j==col)&&board[i][j]==board[row][col])
                    return false;
        }      
       
        return true;           
    }
};


//second flavor
class Solution {
public:
    typedef vector<vector<char> > BOARDTYPE;
   
    void solveSudoku(BOARDTYPE &board) {
        solveSudokuRe(board, 0, 0);
    }
   
    bool solveSudokuRe(BOARDTYPE &board, int row, int col) {
        getNextEmpty(board, row, col);
        if (row == 9) return true;
        vector<bool> avail(9, true);
        getAvailable(board, avail, row, col);
        for (int i = 0; i < 9; ++i)
        {
            if (!avail[i]) continue;
            board[row][col] = i + '1';
            if (solveSudokuRe(board, row, col)) return true;
        }
        board[row][col] = '.';
        return false;
    }
   
    void getNextEmpty(BOARDTYPE &board, int &row, int &col) {
        do {
            if (board[row][col] == '.') return;
            row = (col == 8) ? row + 1 : row;
            col = (col + 1) % 9;
        } while (row < 9);
    }
   
    void getAvailable(BOARDTYPE &board, vector<bool> &avail, int row, int col) {
        for (int i = 0; i < 9; ++i) {
            if (board[row][i] != '.') avail[board[row][i]-'1'] = false;
            if (board[i][col] != '.') avail[board[i][col]-'1'] = false;
            int box_i = row/3*3 + i/3, box_j = col/3*3 + i%3;
            if (board[box_i][box_j] != '.') avail[board[box_i][box_j]-'1'] = false;
        }
    }
};

//third one, a little slower than the two above.
class Solution {
public:
    bool isValid(vector<vector<char> > &board, int x, int y)
    {
        int i, j;
        for (i = 0; i < 9; i++)
            if (i != x && board[i][y] == board[x][y])
                return false;
        for (j = 0; j < 9; j++)
            if (j != y && board[x][j] == board[x][y])
                return false;
        for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
            for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
                if (i != x && j != y && board[i][j] == board[x][y])
                    return false;
        return true;
    }
    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 = 1; k <= 9; ++k)
                    {
                        board[i][j] = '0' + k;
                        if (isValid(board, i, j) && solveSudoku(board))
                            return true;
                        board[i][j] = '.';
                    }
                    return false;
                }
            }
        return true;
    }
};