题目：
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. （Hard）
分析：
DFS搜索，但是不太好写。依次尝试所有可能的数字，然后递归地继续向后添加，发现当填入任何数字都无法满足条件（行列九宫格）后返回false（说明前面填错了）。
想清楚递归地过程的话也不是很难理解。
注意事项：
1.每个数字添加后判断本行，本列和所在九宫格即可，不必判断所有数独内容；
2.自己依照上一题isValid函数写的条件判定代码。导致少了一个board[i][j] != '.'的判断（见代码注释部分），导致所有情况都返回false（因为其会对flag['.' - '0']赋值为1，然后判断等于1）这里错了好久才发现。
代码：
class Solution {
private:
bool isValid (vector<vector<char>>& board, int x, int y) {
int flag[] = {};
for (int i = ; i < board.size(); ++i) {
if (board[x][i] != '.') { //少了这句会导致这个判断总是false!!!
if (flag[board[x][i] - ''] == ) {
return false;
}
else {
flag[board[x][i] - ''] = ;
}
}
}
memset(flag,,sizeof(flag));
for (int i = ; i < board.size(); ++i) {
if (board[i][y] != '.') {
if (flag[board[i][y] - ''] == ) {
return false;
}
else {
flag[board[i][y] - ''] = ;
}
}
}
memset(flag,,sizeof(flag));
int sqx = (x / ) * ;
int sqy = (y / ) * ;
for (int i = sqx; i < sqx + ; ++i) {
for (int j = sqy; j < sqy + ; ++j) {
if (board[i][j] != '.') {
if (flag[board[i][j] - ''] == ) {
return false;
}
else {
flag[board[i][j] - ''] = ;
}
}
}
}
return true;
}
bool solvehelper(vector<vector<char>>& board) {
for (int i = ; i < board.size(); ++i) {
for (int j = ; j < board.size(); ++j) {
if (board[i][j] == '.') {
for (int k = ; k < ; ++k) {
board[i][j] = '' + k;
if (isValid(board, i, j)) {
if (solvehelper(board)) {
return true;
}
}
}
board[i][j] = '.';
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
bool b = solvehelper(board);
}
};