题目链接：Sudoku Solver

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.

这道题的要求是填充数独，其中空位置用‘.’填充，有唯一解。

这道题算是Valid Sudoku的升级版，同样的地方是可以使用3个数组记录每行、每列、每个九宫格出现过的数字。要填充数独，就是要对每个空位逐个填写1~9，查看能否解决。这是一个回溯的问题，可以通过递归来解决。

递归回溯前，使用数组place记录数独中的空位置，用used1、used2和used3标记每行、每列、每个九宫格出现过的数字，然后遍历数独，对其进行初始化设置。然后递归进行回溯处理，每次均循环填充1~9，查看能否填写进去。如果可以，递归进入下一位置；否则，尝试填写下一个数字。

时间复杂度：O(???)

空间复杂度：O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution
{
    int used1[9][9], used2[9][9], used3[9][9];
    
public:
    void solveSudoku(vector<vector<char> > &board)
    {
        vector<vector<int>> place;
        for(int i = 0; i < board.size(); ++ i)
            for(int j = 0; j < board[i].size(); ++ j)
            {
                if(board[i][j] == '.')
                    place.push_back({i, j});
                else
                {
                    int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
                    used1[i][num] = used2[j][num] = used3[k][num] = 1;
                }
            }
        
        DFS(board, place, place.size() - 1);
    }

private:
    bool DFS(vector<vector<char>> &board, vector<vector<int>> &place, int n)
    {
        if(n < 0)
            return true;

        int i = place[n][0], j = place[n][1];
        
        for(int num = 0; num < 9; ++ num)
        {
            int k = i / 3 * 3 + j / 3;
            if(!used1[i][num] && !used2[j][num] && !used3[k][num])
            {
                used1[i][num] = used2[j][num] = used3[k][num] = 1;
                board[i][j] = num + '0' + 1;
                
                if(DFS(board, place, n - 1))
                    return true;
                
                used1[i][num] = used2[j][num] = used3[k][num] = 0;
                board[i][j] = '.';
            }
        }

        return false;
    }
};