编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
空白格用 '.' 表示。
image
一个数独。
image
答案被标成红色。
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。 - 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
思路：
回溯法+哈希表，和之前判断数独是否合法的题目一样，需要用哈希表记录每行每列每个区域是否出现数字，然后利用回溯法尝试，从哈希表中没有记录的数字开始尝试，这时候需要判断结果是否合法，所以回溯函数返回结果必须是bool类型，如果合法则返回true，不合法返回false，重置元素恢复现场，进入下一个值的迭代寻找，具体实现如下。
class Solution {
public:
bool row_mask[9][9];
bool col_mask[9][9];
bool area_mask[9][9];
int size;
void solveSudoku(vector<vector<char>>& board) {
size=9;
if(!isValid(board))
{
return;
}
solveSudokuCore(board,0,0);
}
bool isValid(vector<vector<char>>& board)
{
memset(row_mask,false,sizeof(row_mask));
memset(col_mask,false,sizeof(col_mask));
memset(area_mask,false,sizeof(area_mask));
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
if(!isdigit(board[i][j]))
{
continue;
}
int num=board[i][j]-'0'-1;
int area=(i/3)*3+j/3;
if(row_mask[i][num] || col_mask[j][num] || area_mask[area][num] )
{
return false;
}
row_mask[i][num]=col_mask[j][num]=area_mask[area][num]=true;
}
}
return true;
}
bool solveSudokuCore(vector<vector<char>>& board,int row,int col)
{
if(row>=size)
{
return true;
}
if(col>=size)
{
return solveSudokuCore(board,row+1,0);
}
int area=(row/3)*3+col/3;
if(board[row][col]=='.')
{
for(int i=0;i<size;i++)
{
if(row_mask[row][i] || col_mask[col][i] || area_mask[area][i])
{
continue;
}
board[row][col]='0'+i+1;
row_mask[row][i]=col_mask[col][i]=area_mask[area][i]=true;
if(solveSudokuCore(board,row,col+1))
{
return true;
}
row_mask[row][i]=col_mask[col][i]=area_mask[area][i]=false;
board[row][col]='.';
}
}
else
{
return solveSudokuCore(board,row,col+1);
}
return false;
}
};
