Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.

Note:
The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.

这道题其实是一个简单的深度优先搜索，太久没写代码，写了好久。。。

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        if(board.empty() || board.size() != 9 || board[0].size() != 9)
            return;
        dfs(board, 0, 0);
    }
    
    void dfs(vector<vector<char>>& board, int i, int j){
        if(i == 9){
            solved = true;
            return;
        }
        if(j == 9){
            dfs(board, i+1, 0);
            return;
        }
        if(board[i][j] == '.'){
            for(int m = 1; m <= 9; m++){
                board[i][j] = '0' + m;
                if(isValid(board, i, j)){
                    dfs(board, i, j+1);
                    if(solved)
                        return;
                }
                board[i][j] = '.';  
            }
        }
        else
            dfs(board, i, j+1);
        
    }
    
    bool isValid(vector<vector<char>>& board, int i, int j){
        for(int m = 0; m < 9; m++){
            if(m != i && board[m][j] == board[i][j]){
                return false;
            }
        }
        for(int m = 0; m < 9; m++){
            if(m != j && board[i][m] == board[i][j]){
                return false;
            }
        }
        int rowIndex = 3*(i/3);
        int colIndex = 3*(j/3);
        for(int m = 0; m < 9; m++){
            int newRow = rowIndex + m/3;
            int newCol = colIndex + m%3;
            if((newRow != i || newCol != j) && board[newRow][newCol] == board[i][j]){
                return false;
            }
        }
        return true;
    }
    private:
        bool solved = false;
};