「刷刷刷」37.解数独

发表于 更新于 分类于

题目

难度：困难

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver

思路

很容易想到使用回溯算法来解题。回溯算法的定义网上很容易能搜到，比较直白的描述是：

  • 就像是探索一个很多个房间的迷宫，每个房间都有很多个门通向别的房间。从入口开始一个门一个门地探索，如果走到了死路，就返回上一个房间去探索其他门，知道找到终点。

根据数独的定义，我们可以用三个二维数组来标记每行、每列、每个 3x3 内 1～9 是否已经使用过。
比如：col[0][3] = 1 就表示第 0 列数字 3 已经使用过了。

这里比较难处理的是 3x3 该如何表示，使用一个三维数组是比较简单的做法，但为了节省空间，可以对横纵坐标进行计算后，用二维数组表示。（当然如果要更进一步节省空间，应该使用一维数组加位运算的方式）

我画了个图来解释找到用一位数组表示 3x3 的过程。将每个 3x3 标记为 0～8，如果 x 轴可以转为 0，1，2，同时 y 轴转为 0，3，6，那么x+y就是序号。那么通过公式：x/3 + y/3*3 就可以将每个小格子的坐标和他们所属的 3x3 的序号对应起来了。

数独

有了三个数组来协助判断某个个字是否可以填入数字 N 之后，就可以进行回溯了。每个格子都可以计算出能填的数字有哪些，每次填入一个数字或是回溯之后，都要更新三个数组，来保证后边填写时的判断还是正确的。

如果还要优化，那么每一次填数字应该从缺少的数字最少的行、列、3x3中开始，这样正确率更高，回溯次数更少。

代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {

    // 注意数组长度是9，1～9 对应数字 0～8
    int[][] col = new int[9][9];
    int[][] row = new int[9][9];
    int[][] box = new int[9][9];

    public void solveSudoku(char[][] board) {

        // 将已经填好的数字初始化进各个数组
        init(board);

        // n 表示每个小格子的序号，依次去尝试填数字
        solveSudoku(board, 0);
    }

    private boolean solveSudoku(char[][] board, int n) {

        // n 是 0～80，81表示已经全部填完，直接返回 true
        if (n == 81) {
            return true;
        }

        // 用 n 表示每个小格子的序号，计算出 x，y 坐标
        int y = n % 9;
        int x = n / 9;

        // 如果是已经填好的数字，就填下一个格子
        if (board[x][y] != '.') {
            return solveSudoku(board, n + 1);
        }

        // 当前小格 从 0～8 去试对不对
        for (int i = 0; i < 9; i++) {

            // 判断当前放格是否可以填入 i，如果可以
            if (checkSudoku(i, x, y)) {

                // 在三个数组中标记 i 已使用
                doMark(board, i, x, y);

                // 递归解决下一个格子
                if (solveSudoku(board, n + 1)) {
                    // 如果后边的格子对了，返回 true 给上一个格子
                    return true;
                } else {
                    // 如果不对，则回溯
                    undoMark(board, i, x, y);
                }
            }
        }

        // 九个数字都试完了还不行，说明前面某个格子填的有错误，返回 false
        return false;
    }

    private boolean checkSudoku(int i, int x, int y) {
        if (row[y][i] == 1 || col[x][i] == 1 || box[x / 3 + y / 3 * 3][i] == 1) {
            return false;
        }
        return true;
    }

    private void doMark(char[][] board, int k, int x, int y) {
        // 注意 0～8 和 1 ～ 9 的转换
        board[x][y] = (char) (k + '1');
        row[y][k] = 1;
        col[x][k] = 1;
        box[x / 3 + y / 3 * 3][k] = 1;
    }

    private void undoMark(char[][] board, int k, int x, int y) {
        row[y][k] = 0;
        col[x][k] = 0;
        box[x / 3 + y / 3 * 3][k] = 0;
        board[x][y] = '.';
    }

    private void init(char[][] board) {
        for (int x = 0; x < 9; x++) {
            for (int y = 0; y < 9; y++) {
                if (board[x][y] != '.') {
                    // 注意 0～8 和 1 ～ 9 的转换
                    int k = board[x][y] - '1';
                    row[y][k] = 1;
                    col[x][k] = 1;
                    box[x / 3 + y / 3 * 3][k] = 1;
                }
            }
        }
    }
}

作者：prik
永久链接： https://trzoey.github.io/blog-prik/algorithmic/37.解数独/
转载请注明出处，谢谢合作💓。