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.

思路：回溯法，当有可行解时返回

代码：

 1 class Solution {
 2     bool isValid(vector<vector<char> >& board, int x, int y)
 3     {
 4         bool flags[9] = {0};
 5         for(int i = 0; i < 9; ++i)
 6             if(board[x][i] >= '1' && board[x][i] <= '9')
 7             {
 8                 if(!flags[board[x][i] - '1'])
 9                     flags[board[x][i] - '1'] = true;
10                 else
11                     return false;
12             }
13         memset(flags, 0, 9);
14         for(int i = 0; i < 9; ++i)
15             if(board[i][y] >= '1' && board[i][y] <= '9')
16             {
17                 if(!flags[board[i][y] - '1'])
18                     flags[board[i][y] - '1'] = true;
19                 else
20                     return false;
21             }
22         int xx = x/3*3;
23         int yy = y/3*3;
24         memset(flags, 0, 9);
25         for(int i = 0; i < 3; ++i)
26             for(int j = 0; j < 3; ++j)
27                 if(board[xx+i][yy+j] >= '1' && board[xx+i][yy+j] <= '9')
28                 {
29                     if(!flags[board[xx+i][yy+j]-'1'])
30                         flags[board[xx+i][yy+j]-'1'] = true;
31                     else
32                         return false;
33                 }
34         return true;
35     }
36 public:
37     bool solveSudoku(vector<vector<char> > &board) {
38         for(int i = 0; i < 9; ++i)
39             for(int j = 0; j < 9; ++j)
40             {
41                 if('.' == board[i][j])
42                 {
43                     for(int k = 1; k <= 9; ++k)
44                     {
45                         board[i][j] = '0' + k;
46                         if(isValid(board, i, j) && solveSudoku(board))
47                             return true;
48                         board[i][j] = '.';
49                     }
50                     return false;
51                 }
52             }
53         return true;
54     }
55 };