今天是小浩算法 “365刷題計(jì)劃” 第95天 。數(shù)獨(dú)相信在座的各位都玩過，那我們?nèi)绾问褂贸绦蛉ヲ?yàn)證一個(gè) 9×9 的數(shù)獨(dú)是有效的呢？一起看下！

01

PART

有效的數(shù)獨(dú)

數(shù)獨(dú)是源自18世紀(jì)瑞士的一種數(shù)學(xué)游戲。是一種運(yùn)用紙、筆進(jìn)行演算的邏輯游戲。玩家需要根據(jù) 9×9 盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個(gè)粗線宮（3*3）內(nèi)的數(shù)字均含1-9，不重復(fù)。

有效的數(shù)獨(dú)：判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

• 數(shù)字 1-9 在每一行只能出現(xiàn)一次。

• 數(shù)字 1-9 在每一列只能出現(xiàn)一次。

• 數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

比如輸入：

[

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

數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用 '.' 表示。

說明:

一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的。

只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

給定數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 。

給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。

畫出來就是下面這樣：

02

PART

題解分析

聊聊數(shù)獨(dú)，很早之前其實(shí)研究過一陣子，還是非常有趣的。解法有很多，包括什么余數(shù)法，摒除法等等。那我們?nèi)绾稳ピu(píng)定一個(gè)數(shù)獨(dú)的難度呢？一般情況下，給定的數(shù)字個(gè)數(shù)越多，數(shù)獨(dú)相對(duì)越簡單。

解題的關(guān)鍵題目中其實(shí)已經(jīng)說了：

• 數(shù)字 1-9 在每一行只能出現(xiàn)一次。

• 數(shù)字 1-9 在每一列只能出現(xiàn)一次。

• 數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

我們要做的就是用程序來完成這個(gè)驗(yàn)證的過程，如何驗(yàn)證？那其實(shí)就兩步：

• 第一步：遍歷數(shù)獨(dú)中的每一個(gè)元素

• 第二步：驗(yàn)證該元素是否滿足上述條件

遍歷這個(gè)沒什么好說的，從左到右，從上到下進(jìn)行遍歷即可。就一個(gè)兩層循環(huán)。因?yàn)轭}目本身就是常數(shù)級(jí)的規(guī)模，所以時(shí)間復(fù)雜度就是 O(1)。

問題來了：如何驗(yàn)證元素在 行 / 列 / 子數(shù)獨(dú)中沒有重復(fù)項(xiàng)？

其實(shí)很簡單，我們建立三個(gè)數(shù)組分別記錄每行，每列，每個(gè)子數(shù)獨(dú)（子數(shù)獨(dú)就是上面各種顏色的小框框）中出現(xiàn)的數(shù)字。

1//JAVA 2int[][]?rows?=?new?int[9][9]; 3int[][]?col?=?new?int[9][9]; 4int[][]?sbox?=?new?int[9][9];

當(dāng)然，剛開始的時(shí)候他們都是空的。然后每遍歷到一個(gè)元素，我們就看看這個(gè)元素在里邊存不存在，不存在就放進(jìn)去，存在那說明數(shù)獨(dú)不合法。

舉個(gè)栗子，比如這個(gè)數(shù)獨(dú)。第6行5列為2，那我們就對(duì) rows 和 col 進(jìn)行設(shè)置：（1表示元素存在）

rows[當(dāng)前行][當(dāng)前元素值] = rows[5][2] = 1

col[當(dāng)前列][當(dāng)前元素值] = col[4][2] = 1

但是這里有個(gè)問題，如果元素值是 9，那就越界了！所以我們對(duì)當(dāng)前元素值減個(gè)一處理一下：

rows[當(dāng)前行][當(dāng)前元素值] = rows[5][2-1] = 1

col[當(dāng)前列][當(dāng)前元素值] = col[4][2-1] = 1

現(xiàn)在的題是，對(duì)于 sbox 該如何設(shè)置呢？我們用下面的公式來計(jì)算得到：

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

其實(shí)很容易理解：我們把上面的第6行5列代入到這個(gè)公式里，(5 / 3) * 3 + 4 / 3 = 3 + 1 = 4。這個(gè) 4 也就代表最終落到 4 的這個(gè)小區(qū)域中。

我猜有人不能理解這個(gè)算式（是的，連公式都稱不上），所以我再解釋一下它是怎么來的。比如上面的第 6 行，row 為 5，5/3=1 可以理解為 此時(shí)在第1大行上，然后 (5/3)*3，是計(jì)算出當(dāng)前第一大行處的 boxIndex 值。最后再加上的 4/3，意思是向右偏移幾個(gè)大列。

根據(jù)分析，給出代碼：

1class?Solution?{2????public?boolean?isValidSudoku(char[][]?board)?{3????????int[][]?rows?=?new?int[9][9];4????????int[][]?col?=?new?int[9][9];5????????int[][]?sbox?=?new?int[9][9];6????????for?(int?i?=?0;?i?<?board.length;?i++)?{7????????????for?(int?j?=?0;?j?<?board[0].length;?j++)?{8????????????????if?(board[i][j]?!=?'.')?{9????????????????????int?num?=?board[i][j]?-?'1'; 10????????????????????int?boxIndex?=?(i?/?3)?*?3?+?j?/?3; 11????????????????????if?(rows[i][num]?==?1)?return?false; 12????????????????????rows[i][num]?=?1; 13????????????????????if?(col[j][num]?==?1)?return?false; 14????????????????????col[j][num]?=?1; 15????????????????????if?(sbox[boxIndex][num]?==?1)?return?false; 16????????????????????sbox[boxIndex][num]?=?1; 17????????????????} 18????????????} 19????????} 20????????return?true; 21????} 22}

鄭重申明（讀我的文章必看）：

• 本系列所有教程都不會(huì)用到復(fù)雜的語言特性，大家無須擔(dān)心沒有學(xué)過相關(guān)語法，算法思想才是最重要的！

• 作為學(xué)術(shù)文章，雖然風(fēng)格可以風(fēng)趣，但嚴(yán)謹(jǐn)，我是認(rèn)真的。本文所有代碼均在leetcode進(jìn)行過測(cè)試運(yùn)行。

03

PART

啰嗦一下

母親節(jié)快樂~

最后，我在這里分享給大家一個(gè)很難很難的數(shù)獨(dú)，歡迎大家來挑戰(zhàn)！！挑戰(zhàn)成功的，評(píng)論區(qū)留下你的答案！

好了，今天的題目就講完了，我覺得講的還是挺好的。大家要是認(rèn)為ok的話，給我來個(gè)轉(zhuǎn)發(fā)吧~感謝！如果想看其他面試題相關(guān)內(nèi)容的，可以看：

漫畫：知乎面試題（旋轉(zhuǎn)數(shù)組最小值Ⅰ - 基礎(chǔ)版）

漫畫：知乎面試題（旋轉(zhuǎn)數(shù)組最小值Ⅱ - 進(jìn)階版）

漫畫：美團(tuán)面試題（TOPK：求第K個(gè)最大的元素）

漫畫：騰訊面試題（面試官問我會(huì)不會(huì)修供暖器，我說沒問題）

漫畫：位運(yùn)算技巧整理匯總+一道被嫌棄的題目

如果你問我對(duì)學(xué)習(xí)算法有什么建議，這篇文章是必看的：

漫畫：小白為了面試如何刷題？（嘔心瀝血算法指導(dǎo)篇）

漫畫：嘔心泣血算法指導(dǎo)篇（真正的干貨，怒懟那些說算法沒用的人）

?小浩算法，每日一題

關(guān)注領(lǐng)取《圖解算法題》高清版

進(jìn)群的小伙伴請(qǐng)加右側(cè)私人微信（備注：進(jìn)群）

總結(jié)

以上是生活随笔為你收集整理的漫画：算法如何验证合法数独 | 全世界最难的数独？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。