Valid Sudoku 是个简单的遍历问题，只要每次遍历每一行 每一列 每一个方块 判断合法性即可
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
bool ish[10];
int len=board.size();
for(int i=0;i<len;i++){
memset(ish,0,sizeof(ish));
for(int j=0;j<len;j++){
if(board[i][j]=='.')continue;
if(ish[board[i][j]-'0'])return false;
ish[board[i][j]-'0']=true;
}
memset(ish,0,sizeof(ish));
for(int j=0;j<len;j++){
if(board[j][i]=='.')continue;
if(ish[board[j][i]-'0'])return false;
ish[board[j][i]-'0']=true;
}
memset(ish,0,sizeof(ish));
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
if(board[(i/3)*3+j][(i%3)*3+k]=='.')continue;
if(ish[board[(i/3)*3+j][(i%3)*3+k]-'0'])return false;
ish[board[(i/3)*3+j][(i%3)*3+k]-'0']=true;
}
}
}
return true;
}
};
Sudoku Solver 也可以看成是个回溯题，类似八皇后的求法，每次选取一个空格，列举在本行、本列及其本方块内可以使用的数，如果可以向下一个方块执行，否则退回。
class Solution {
public:
bool isValid(vector<vector<char> > &board, int a, int b) {
int i,j;
for(i = 0; i < 9; i++)
if(i != a && board[i][b] == board[a][b])
return false;
for(j = 0; j < 9; j++)
if(j != b && board[a][j] == board[a][b])
return false;
int x = a/3*3;
int y = b/3*3;
for(i = 0; i < 3; i++)
for(j = 0; j< 3; j++)
if(x+i != a && y+j != b && board[x+i][y+j] == board[a][b])
return false;
return true;
}
bool solveSudokudfs(vector<vector<char> > &board)
{
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
{
if(board[i][j] == '.')
{
for(int k = 1; k <= 9; k++)
{
board[i][j] = '0' + k;
if(isValid(board,i,j) && solveSudokudfs(board))
return true;
board[i][j] = '.';
}
return false;
}
}
return true;
}
void solveSudoku(vector<vector<char> > &board) {
// Note: The Solution object is instantiated only once.
solveSudokudfs(board);
}
};