漫画：算法如何验证合法数独 | 全世界最难的数独？

程序员小浩

发布于 2020-05-26 11:17:09

7960

发布于 2020-05-26 11:17:09

文章被收录于专栏：小浩算法

今天是小浩算法 “365刷题计划” 第95天。数独相信在座的各位都玩过，那我们如何使用程序去验证一个 9×9 的数独是有效的呢？一起看下！

PART

有效的数独

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据 9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

有效的数独：判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

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

比如输入：

[

["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"]

]

输出: true

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

说明:

一个有效的数独（部分已被填充）不一定是可解的。

只需要根据以上规则，验证已经填入的数字是否有效即可。

给定数独序列只包含数字 1-9 和字符 '.' 。

给定数独永远是 9x9 形式的。

画出来就是下面这样：

PART

题解分析

聊聊数独，很早之前其实研究过一阵子，还是非常有趣的。解法有很多，包括什么余数法，摒除法等等。那我们如何去评定一个数独的难度呢？一般情况下，给定的数字个数越多，数独相对越简单。

解题的关键题目中其实已经说了：

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

我们要做的就是用程序来完成这个验证的过程，如何验证？那其实就两步：

第一步：遍历数独中的每一个元素
第二步：验证该元素是否满足上述条件

遍历这个没什么好说的，从左到右，从上到下进行遍历即可。就一个两层循环。因为题目本身就是常数级的规模，所以时间复杂度就是 O(1)。

问题来了：如何验证元素在行 / 列 / 子数独中没有重复项？

其实很简单，我们建立三个数组分别记录每行，每列，每个子数独（子数独就是上面各种颜色的小框框）中出现的数字。

//JAVA
int[][] rows = new int[9][9];
int[][] col = new int[9][9];
int[][] sbox = new int[9][9];

当然，刚开始的时候他们都是空的。然后每遍历到一个元素，我们就看看这个元素在里边存不存在，不存在就放进去，存在那说明数独不合法。

举个栗子，比如这个数独。第6行5列为2，那我们就对 rows 和 col 进行设置：（1表示元素存在）

rows[当前行][当前元素值] = rows[5][2] = 1

col[当前列][当前元素值] = col[4][2] = 1

但是这里有个问题，如果元素值是 9，那就越界了！所以我们对当前元素值减个一处理一下：

rows[当前行][当前元素值] = rows[5][2-1] = 1

col[当前列][当前元素值] = col[4][2-1] = 1

现在的题是，对于 sbox 该如何设置呢？我们用下面的公式来计算得到：

boxIndex = (row / 3) * 3 + columns / 3

其实很容易理解：我们把上面的第6行5列代入到这个公式里，(5 / 3) * 3 + 4 / 3 = 3 + 1 = 4。这个 4 也就代表最终落到 4 的这个小区域中。

我猜有人不能理解这个算式（是的，连公式都称不上），所以我再解释一下它是怎么来的。比如上面的第 6 行，row 为 5，5/3=1 可以理解为 此时在第1大行上，然后 (5/3)*3，是计算出当前第一大行处的 boxIndex 值。最后再加上的 4/3，意思是向右偏移几个大列。

根据分析，给出代码：

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] col = new int[9][9];
        int[][] sbox = new int[9][9];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int boxIndex = (i / 3) * 3 + j / 3;
                    if (rows[i][num] == 1) return false;
                    rows[i][num] = 1;
                    if (col[j][num] == 1) return false;
                    col[j][num] = 1;
                    if (sbox[boxIndex][num] == 1) return false;
                    sbox[boxIndex][num] = 1;
                }
            }
        }
        return true;
    }
}