LeetCode 图解 | 37.解数独

痛定思痛。 2023-07-08 02:59 106阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

今天分享一个LeetCode题，题号是37，题目标题是解数独，题目标签是散列表和回溯算法。

### 题目描述 ###

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

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

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

空白格用 '.' 表示。

![一个数独][format_png 2]

一个数独

一个数独。

![答案被标成红色][format_png 3]

答案被标成红色

答案被标成红色。

**Note:**

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

### 解题 ###

此题题目标签是散列表和回溯算法，但我觉得散列表换成直接寻址表更巴适。因为一个数独只有1~9的数字。

回到题目描述，一个数独的解法需要遵循以下规则：

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

使用直接寻址表，可以设计成

数字：Booleal类型[27个空间默认为False]

假设行的下标为i，列的下标为j，宫格的索引为k，某数字的i、j+9和k+18下标只能出现true一次，下次判断时出现同样的true就不满足一个有解的数独了。

下标i和下标j可以从行和列中直接获取，那宫格的索引k又如何获取呢？看下面图：

![format_png 4][]

三下标的索引

k随着i变化和k随着j变化都有规律的，不多说，直接给公式：k = (int)(i / 3) \* 3 + (int)(j / 3)。

要注意的是board二维数组保存的是字符，需换成相应的整数。代码如下：

boolean[][] address = new boolean[9][27]; // 默认false
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int index = board[i][j] - '1'; // board数组保存的是字符，需换成相应的整数
                // 宫格的索引
                int k = i / 3 * 3 + j / 3;
                // 记录某数字存放的位置
                address[index][i] = true;
                address[index][j + 9] = true;
                address[index][k + 18] = true;
            }
        }
    }

得出来的address的值如下：

下标 : 值[一维数组]
    0 : F T F F T F F T F F F F T T F F F T F T F F F T F T F
    1 : F F F F F T T F F F F F F T F T F F F F F F T F F F T
    2 : T F F T T F F F F F T F F F T F F T T F F F T T F F F
    3 : F F F F T F F T F T F F T F F F F F F F F T F F F T F
    4 : T T F F F F F T F T F F F F T F F T T T F F F F F F T
    5 : F T T T F T T F F T T F F T F F T T T F T F T T T F F
    6 : T F F F F T F F T T F F F T F F T F F T F T F F F F T
    7 : F F T T T F T F T T F T T T F F T F T F F T T F F T T
    8 : F T T F F F F T T F T F F T T F F T T T F F F F F T T

我在前几篇写过LeetCode第36号题，是直接使用散列表（哈希表）做这道题，[文章的动画视频][Link 1] 如下：

##### 动画：散列表，也可以用直接寻址表表示 #####

散列表和直接寻址表的区别，在于散列表保存的是键值对，直接寻址表保存的是值，键在数组的下标上，所以数据的键是比较好看的范围不是很大的，也是可以用直接寻址表的，如26个字母。散列表的时间复杂度和直接寻址表是同等的，都是为O(1)。

回溯算法和上一篇算法动画文章类似，可以传送到 [这篇文章][Link 2] 回一下回溯算法代码的框架。

回溯算法在树底部会得出结果，相应地，满足结束条件会放在树底下。

##### 动画：LeetCode17号题使用回溯算法 #####

回溯算法要注重三个过程，第一个是找到需要满足的结束条件，第二找到选择路径，第三找到待选择列表。

第一个很简单，全部遍历这个数独就可以满足结束条件了，代码如下；

// 找寻空位置
    while (board[i][j] != '.') {
        if (++j >= 9) {
            i++;
            j = 0;
        }
        if (i >= 9) return true; // 到这里说明数独已填入的数字是有解的
                                 // 不能返回为空，返回为空会破坏掉已填入的数字 
    }

第二个是在空格上选择路径，从待选择列表选择一个路径，但需要将待选择列表排除掉当前不满足规则的数字；

第三个是继续往下走时直到没有选择路径可选，在判断是否已经全部遍历这个数独了，如果没有需要回溯到其它路径上。

##### 动画：有解数独使用回溯算法 #####

##### Code #####

public void solveSudoku(char[][] board) {
        // 创建直接寻址表 记录某数字存放的位置 空间换时间
        boolean[][] address = new boolean[9][27];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int index = board[i][j] - '1'; // board数组保存的是字符，需换成相应的整数
                    // 宫格的索引
                    int k = i / 3 * 3 + j / 3;
                    // 记录某数字存放的位置
                    address[index][i] = true;
                    address[index][j + 9] = true;
                    address[index][k + 18] = true;
                }
            }
        }
        // 回溯算法，和dfs类似，dfs一般做遍历，没有回溯
        track(board, address, 0, 0);
    }
    
    private boolean track(char[][] board, boolean[][] address, int i, int j) {
        // 找寻空位置
        while (board[i][j] != '.') {
            if (++j >= 9) {
                i++;
                j = 0;
            }
            if (i >= 9) return true; // 到这里说明数独已填入的数字是有解的
        }
        for (int index = 0; index < 9; index++) {
            // 宫格索引
            int k = i / 3 * 3 + j / 3;
            if (!address[index][i] && !address[index][j + 9] && !address[index][k + 18]) {
                // index 与 行 列 宫格索引不冲突
                // 填入 index，要注意换成对应字符
                board[i][j] = (char) (index + '1');
                address[index][i] = true;
                address[index][j + 9] = true;
                address[index][k + 18] = true;
                // 递归
                if (track(board, address, i, j))
                    return true;
                // 回溯
                board[i][j] = '.';
                address[index][i] = false;
                address[index][j + 9] = false;
                address[index][k + 18] = false;
                }
            }
        }
        return false; // 当前位置与所有index数字冲突，直接返回false，回到上一个空格
    }

##### 执行结果 #####

执行用时 : 2 ms , 在所有 Java 提交中击败了 96.94% 的用户
    内存消耗 : 34.6 MB , 在所有 Java 提交中击败了 94.14% 的用户

**END**

--------------------

![format_png 5][]

● [深度剖析头条面试真题 | 二叉树那点事儿][Link 3]

[● ][Link 4][牛逼了，原来大神都是这样学动态规划的...][...]

● [不上班的 613 天][613]

● [数据结构和算法学习指南][Link 5]

![format_png 6][]

点“在看”你懂得

![format_png 7][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9ENjdwZWNlaWJlSVJiTkp1c21LYU5tck9QRTdjeDA3bUF3SWVDd1VmenY4T1RCWElOakNOaWJ6aGJJSGhjaWNmMkI5aWFXUUtEZDdkbjZwaWNPaWNZVVpwWUVwZy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbUUydW8zY25pY2V3bWljdGlhbEJ0SmNaZ2dXZUx2c251cmljWDRpYUN2WUdFdEM4VzduUVhDRkRiaWNXWjU5MllzYldZUHc2dlRpYTN6WGxBd3cvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbUUydW8zY25pY2V3bWljdGlhbEJ0SmNaZ2liVDl4YXNWcW5DNmliVXY1bWFQQjNmajlVYTdlUmQ5R3V0VWIzOENjZ2J2TXN3TWdNcDJETFpRLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbUUydW8zY25pY2V3bWljdGlhbEJ0SmNaZ0RTczdHUlpFQ0czMWRKeXd6dVF6RlRRMDRDbzFpYm1jamZ6NkpzZjBmSDhHeUJQdnI1Q0N2ZEEvNjQw?x-oss-process=image/format,png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU3MDkxMDg2OA%3D%3D&chksm=fce97247cb9efb51017e690054d603d1e96ba445e0b39972b782dd61049a47a15a983510658d&idx=1&mid=2247484348&scene=21&sn=0ee2916e33a30b2f4bb948251a1272bf#wechat_redirect
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/103080962
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9wNldsMkxETVFsSEM2cERYeVFSYVdqbFdSNVBJaHVrSVVHVjFuZks2SDlxdEhab3huWHRWZGV6dG9GZXhrYWV2dWRtWjFNYlY5cVdOWlRYaWFvcEx5b1EvNjQw?x-oss-process=image/format,png
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/104453953
[Link 4]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[...]: https://blog.csdn.net/kexuanxiu1163/article/details/104438052
[613]: https://blog.csdn.net/kexuanxiu1163/article/details/104421485
[Link 5]: https://blog.csdn.net/kexuanxiu1163/article/details/104385939
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jNmdxbWhXaWFmeXI5djFSblJIZGdiRTlWTzljY2pWU0FuOGpxUXBoeUxKbDU5N1JzOUJ6RVViQlIwQUdmSmZ2a3pMOXJ1cWtUbVBBWHIyOXRISWNwRFEvNjQw?x-oss-process=image/format,png