点击上方蓝字设为星标LeetCode 图解 | 37.解数独

下面开始今天的学习~

LeetCode 图解 | 37.解数独

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

题目描述

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

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

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

空白格用 ‘.’ 表示。

LeetCode 图解 | 37.解数独

一个数独

一个数独。

LeetCode 图解 | 37.解数独

答案被标成红色

答案被标成红色。

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又如何获取呢?看下面图:

LeetCode 图解 | 37.解数独

三下标的索引

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号题,是直接使用散列表(哈希表)做这道题,文章的动画视频 如下:

动画:散列表,也可以用直接寻址表表示
散列表和直接寻址表的区别,在于散列表保存的是键值对,直接寻址表保存的是值,键在数组的下标上,所以数据的键是比较好看的范围不是很大的,也是可以用直接寻址表的,如26个字母。散列表的时间复杂度和直接寻址表是同等的,都是为O(1)。
回溯算法和上一篇算法动画文章类似,可以传送到 这篇文章 回一下回溯算法代码的框架。
回溯算法在树底部会得出结果,相应地,满足结束条件会放在树底下。
动画:LeetCode17号题使用回溯算法
回溯算法要注重三个过程,第一个是找到需要满足的结束条件,第二找到选择路径,第三找到待选择列表。
第一个很简单,全部遍历这个数独就可以满足结束条件了,代码如下;
// 找寻空位置
while (board[i][j] != '.') {
    if (++j >= 9) {
        i++;
        j = 0;
    }
    if (i >= 9return 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, 00);
}

private boolean track(char[][] board, boolean[][] address, int i, int j) {
    // 找寻空位置
    while (board[i][j] != '.') {
        if (++j >= 9) {
            i++;
            j = 0;
        }
        if (i >= 9return 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



LeetCode 图解 | 37.解数独

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

● 牛逼了,原来大神都是这样学动态规划的…

● 不上班的 613 天

数据结构和算法学习指南


LeetCode 图解 | 37.解数独


点“在看你懂得 

LeetCode 图解 | 37.解数独

原文始发于微信公众号(五分钟学算法):LeetCode 图解 | 37.解数独