LeetCode 37 解数独（dfs）

题目链接：解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

思路

经典的解数独游戏。

首先记录下来所有的需要填数字的坐标信息，然后从第一个需要填数的地方开始填数，依次判断数字 1-9 ，当前位置是否可以填数，可以的话填数，继续搜索下一层，最后回溯的时候需要取消填数继续试。如果找到答案，就记录一下，这里可以剪枝。

要判断一个地方能不能填数字，要满足：

这一行中有没有相同数字
这一列中有没有相同数字
当前的小9宫格中，有没有相同数字（对当前坐标*3和/3的操作是为了确定当前小九宫格的起始点坐标）

如果满足这个条件，证明这个地方可以填数。

具体看代码

代码

 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
51
class Solution
{
public:
    vector<pair<int, int>> point;
    vector<vector<char>> ans;
    bool flag;
    bool check(vector<vector<char>> &board, int k, int step)
    {
        for (int i = 0; i < 9; i++)
            if (board[point[step].first][i] - '0' == k || board[i][point[step].second] - '0' == k)
                return false;
        // 计算当前所在的小九宫格坐标
        int x = (point[step].first / 3) * 3;
        int y = (point[step].second / 3) * 3;
        for (int i = x; i < x + 3; i++)
            for (int j = y; j < y + 3; j++)
                if (board[i][j] - '0' == k)
                    return false;
        return true;
    }
    void dfs(vector<vector<char>> &board, int step)
    {
        if (flag)
            return;
        if (step == point.size())
        {
            flag = true;
            ans = board;
            return;
        }
        for (int i = 1; i <= 9; i++)
        {
            if (check(board, i, step))
            {
                board[point[step].first][point[step].second] = i + '0';
                dfs(board, step + 1);
                board[point[step].first][point[step].second] = '.';
            }
        }
    }
    void solveSudoku(vector<vector<char>> &board)
    {
        flag = false;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.')
                    point.push_back({i, j});
        dfs(board, 0);
        board = ans;
    }
};

最后修改于 2020-09-15

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。