leetcode37.解数独

Posted on | In |
Words count in article: 848 | Reading time ≈ 4

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

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

    1. 数字 1-9 在每一行只能出现一次。
    2. 数字 1-9 在每一列只能出现一次。
    3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

    数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

1
2
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

分析：

1
2
- 搜索顺序： 按行搜索每个单元
- 剪枝条件： 行、列，单元格不重复出现

代码

  • C++

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
class Solution {
public:

    bool row[9][9], col[9][9], cell[3][3][9]; // 记录行、列和单元格出现的数字

    bool dfs(vector<vector<char>>& board, int x, int y) {
        if (y == 9) x ++, y = 0; // 换行
        if (x == 9) return true; // 搜索完毕

        if (board[x][y] != '.') dfs(board, x, y + 1); //单元为空才搜索
        // 枚举数字，看单元可以填充那个数字
        for (int i = 0;i < 9;i ++) {
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                board[x][y] = '1' + i;
                if (dfs(board, x, y + 1)) return true;
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
                board[x][y] = '.';
            }
        }

        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(row, false, sizeof row);
        memset(col, false, sizeof col);
        memset(cell, false, sizeof cell);

        for (int i = 0;i < 9;i ++)
            for (int j = 0;j < 9;j ++) {
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
            }

        dfs(board, 0, 0);
    }
};

[原题链接](37. 解数独 - 力扣（Leetcode）)

0%