Sudoku Solver

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.

Runtime: 72ms.

 1 class Solution {
 2 public:
 3     void solveSudoku(vector<vector<char>>& board) {
 4         if(board.empty() || board.size() != 9 || board[0].size() != 9)  return;
 5         
 6         solve(board, 0, 0);
 7     }
 8     
 9     bool solve(vector<vector<char> >& board, int i, int j){
10         if(j >= 9) //reaches to the last column
11             return solve(board, i + 1, 0);
12         
13         if(i == 9) //reaches to the last row
14             return true;
15             
16         if(board[i][j] == '.'){//fill 0~9 recursively
17             for(int k = 1; k <= 9; k++){
18                 board[i][j] = k + '0';
19                 if(isValid(board, i, j)){
20                     if(solve(board, i, j + 1))
21                         return true;
22                 }
23                 board[i][j] = '.'; //this line is important?
24             }
25         }
26         else
27             return solve(board, i, j + 1);
28         
29         return false;
30     }
31     
32     bool isValid(vector<vector<char> >& board, int i, int j){
33         for(int row = 0; row < 9; row++){
34             if(row != i && board[row][j] == board[i][j])
35                 return false;
36         }
37         
38         for(int col = 0; col < 9; col++){
39             if(col != j && board[i][col] == board[i][j])
40                 return false;
41         }
42         
43         for(int row = i / 3 * 3; row < i / 3 * 3 + 3; row++){
44             for(int col = j / 3 * 3; col < j / 3 * 3 + 3; col++){
45                 if((row != i || col != j) && board[row][col] == board[i][j])
46                     return false;
47             }
48         }
49         
50         return true;
51     }
52 };