算法1

(DFS) $(9!)^9$

1. 先对已经存在数组中的数进行在每一行、每一列、每一个3*3的小矩阵里进行 ++
2. 然后从0, 0开始进行深搜
3. 对于遇到的为’.’的地方时从1到9依次赋给它，每一次要进行判断是否符合条件
4. 如果符合条件则继续深搜，否则回溯，恢复现场
5. 如果碰到不是’.’的地方，直接搜下一个点就行了

C++ 代码

class Solution {
public:
    int row[9][10] = {0};
    int col[9][10] = {0};
    int box[9][10] = {0};
    void solveSudoku(vector<vector<char>>& board) {
        //预处理原数组中的数字
        for (int i = 0; i < 9; i ++)
        {
            for (int j = 0; j < 9; j ++)
            {
                char c = board[i][j];
                if (c != '.')
                {
                    row[i][c - '0'] ++;
                    col[j][c - '0'] ++;
                    box[(i / 3) * 3 + j / 3][c - '0'] ++;
                }
            }
        }

        //从0，0开始深搜
        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>>& board, int x, int y)
    {
        //每次y ++ 如果 y 加到了头，y就要从头开始，即x ++, y = 0
        if (y > 8) y = 0, x ++;
        //如果 x > 8 说明已经全部遍历结束且都符合要求
        if (x > 8) return true;

        //如果是 '.' 的话
        if (board[x][y] == '.')
        {
            for (char ch = '1'; ch <= '9'; ch ++)
            {
                if (!check(ch, x, y))
                {
                    board[x][y] = ch;
                    row[x][ch - '0'] ++;
                    col[y][ch - '0'] ++;
                    box[(x / 3) * 3 + y / 3][ch - '0'] ++;

                    if (dfs(board, x, y + 1)) return true;

                    //回溯(恢复现场)
                    board[x][y] = '.';
                    row[x][ch - '0'] --;
                    col[y][ch - '0'] --;
                    box[(x / 3) * 3 + y / 3][ch - '0'] --;
                }
            }
        }
        else return dfs(board, x, y + 1);

        return false;
    }

    //检查点是否符合条件
    bool check(char t, int x, int y)
    {
        return row[x][t - '0'] || col[y][t - '0'] || box[(x / 3) * 3 + y / 3][t - '0'];
    }
};