[Leetcode]Sudoku Solver&&Valid Sudoku

数独游戏。规则很简单，每行每列以及9个小方格里的1-9数字不能重复。判断所给序列是否为合法的数独序列，按照规则判断即可。

代码如下：

class Solution {
public:
    bool isValidRow(vector<vector<char> > &board){
        int counter[10]={0};
        for(int i=0;i<9;i++){
            memset(counter,0,sizeof(int)*10);
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'){
                   counter[board[i][j]-'0']++;
                   if(counter[board[i][j]-'0']>1){
                    return false;
                   }
                }
            }
        }
        return true;
        
    }
    bool isValidColumn(vector<vector<char> > &board){
        int counter[10]={0};
        for(int i=0;i<9;i++){
            memset(counter,0,sizeof(int)*10);
            for(int j=0;j<9;j++){
                if(board[j][i]!='.'){
                    counter[board[j][i]-'0']++;
                    if(counter[board[j][i]-'0']>1){
                        return false;
                    }
                }
            }
        }
        return true;
    }
    bool isValidSubbox(vector<vector<char> > &board){
        int counter[10]={0};
        int step[9][2]={{0,0},{0,1},{0,1},{1,0},{1,0},{0,-1},{0,-1},{-1,0},{0,1}};
        for(int i=0;i<9;i+=3){
			for(int j=0;j<9;j+=3){
                memset(counter,0,sizeof(int)*10);
                int m=i,n=j;
                for(int k=0;k<9;k++){
                     m+=step[k][0];
                     n+=step[k][1];
                     if(board[m][n]!='.'){
                        counter[board[m][n]-'0']++;
                        if(counter[board[m][n]-'0']>1){
                            return false;
                        }
                    }
                }
		   }
        }
        return true;
    }
    bool isValidSudoku(vector<vector<char> > &board) {
        int m=board.size();
        if(m==0){
            return true;
        }
        return isValidRow(board)&&isValidColumn(board)&&isValidSubbox(board);
    }
};

解决数独，运用深度优先遍历，找出需要填数字的位置，对于每个位置，填充1-9数字，遇到不能填充的，回溯。

代码如下：

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        vector<int> empty;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.'){
                    empty.push_back(i*9+j);
                }
            }
        }
        dfs(board,empty,0);
    }
    bool dfs(vector<vector<char> > &board,vector<int> &empty,int cur){
        if(cur==empty.size()){
            return true ;
        }
        int fillNum=empty[cur];
        int row=fillNum/9;
        int column=fillNum%9;
        for(int i=1;i<=9;i++){
            if(isValid(board,row,column,i)){
                board[row][column]=i+'0';
            if(dfs(board,empty,cur+1)){
                return true;
            }
            board[row][column]='.';
            }
        }
        return false;
    }
    bool isValid(vector<vector<char> > &board,int row,int column,int num){
        for(int i=0;i<9;i++){
            if(board[row][i]-'0'==num){
                return false;
            }
            if(board[i][column]-'0'==num){
                return false;
            }
            int sub_row=3*(row/3)+i/3;
            int sub_column=3*(column/3)+i%3;
            if(board[sub_row][sub_column]-'0'==num){
                return false;
            }
        }
        return true;
        
    }
     
        
};