编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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;
    }
};