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

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

dfs,一直寻找，不行返回即可：

1 class Solution { 2 public: 3     void solveSudoku(vector
     
      
       >& board) { 4         doSudoku(board); 5     } 6  7     bool checkValid(vector
       
        
         >&board, int x, int y) 8     { 9         for(int i = 0; i < 9; i++){10             if(i!=x)11                 if(board[i][y] == board[x][y]) return false;12         }13 14         for(int j = 0; j < 9; j++){15             if(j != y)16                 if(board[x][j] == board[x][y]) return false;17         }18 19         for(int i = (x/3) * 3; i < (x/3 + 1) * 3; ++i){20             for(int j = (y/3) * 3; j < (y/3 + 1) * 3; ++j){21                 if((i!=x) || (j != y))22                     if(board[x][y] == board[i][j]) return false;23             }24         }25         return true;26     }27 28     bool doSudoku(vector
         
          
           > & board)29 {30 for(int row = 0; row < 9; ++row){31 for(int col = 0; col < 9; ++col){32 if(board[row][col] == '.'){33 for(int i = 1; i <= 9; ++i){34 board[row][col] = '0' + i;35 if(checkValid(board, row, col)){36 if(doSudoku(board)){37 return true;38 }39 } 40 board[row][col] = '.';41 }42 return false;43 }44 }45 }46 return true;47 }48 };