专栏首页小浩算法漫画:算法如何验证合法数独 | 全世界最难的数独?

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

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

01

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 形式的。

画出来就是下面这样:

02

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;
    }
}

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

03

PART

最后,我在这里分享给大家一个很难很难的数独,欢迎大家来挑战!!

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 万字长文!位运算面试看这篇就够了!

    祝大家五一快乐。今天是小浩算法 “365刷题计划” 位运算超长 - 整合篇。估计五一期间,大家也没有什么心思好好做题。所以我就把之前已经出过的位运算系列,进行了...

    程序员小浩
  • 漫画:博弈论系列 之 海盗分金币的故事(附:代码实现)

    在面试的过程中,除了常规的算法题目,我们经常也会被问到一些趣味题型来考察思维,尤其以 FLAG(Facebook, LinkedIn, Amazon, Goog...

    程序员小浩
  • 漫画:从赌神梭哈中衍化而来的算法面试题

    拿到题目的小伙伴,可能觉得“我次奥”,这特么也能出一道题 ?不得不说《贱止offer》,嗯....不错!

    程序员小浩
  • P1186 玛丽卡

    题目描述 麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复。 因为她和他们不住在同一个城市,因此她开始准备她的长途旅行。 在这个国家中每两个城市之间最多只有一条...

    attack
  • codeforces 429A(dfs)

    给定一棵树,树的每个结点上有一个值,你可以对树上的值进行异或操作,求使树上的结点值成为目标值所需的最少操作

    dejavu1zz
  • 挑战程序竞赛系列(11):2.5最短路径

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 线段树相关问题 (引用 PKU POJ题目) 整理

    如果(a < b – 1){分别计算a、b的次数和线段树[a + 1, b – 1)的次数,取大(小)的一项};

    owent
  • LWC 52:688. Knight Probability in Chessboard

    LWC 52:688. Knight Probability in Chessboard 传送门:688. Knight Probability in Ches...

    用户1147447
  • 图论-网络流-最大流--POJ1273Drainage Ditches(Dinic)

    Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite...

    风骨散人Chiam
  • 图论--网络流--最大流 POJ 2289 Jamie's Contact Groups (二分+限流建图)

    Jamie is a very popular girl and has quite a lot of friends, so she always keeps...

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券