问题：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.
回答：
bool isValid(vector<vector<char> > &board, int px, int py) {
int len = board.size();
//check rows and cols.
for (int i = 0; i < len; ++i)
{
if(i != py && board[px][i] == board[px][py] ||
i != px && board[i][py] == board[px][py])
return false;
}
//check box
int basex = px/3 * 3;
int basey = py/3 * 3;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
{
if( basex + i != px &&
basey + j != py &&
board[basex + i][basey + j] == board[px][py])
return false;
}
return true;
}
bool currentSudoku(vector<vector<char> > &board) {
for (int row = 0; row < 9; ++row)
for (int col = 0; col < 9; ++col)
{
if(board[row][col] == '.')
{
for(char num = '1'; num <= '9'; ++num)
{
board[row][col] = num;
if(isValid(board, row, col) && currentSudoku(board))
return true;
board[row][col] = '.';
}
return false;//no number can add in this point.
}
}
return true;
}
void solveSudoku(vector<vector<char> > &board) {
currentSudoku(board);
}