[LeetCode] 36. Valid Sudoku

</br>


Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'

A partially filled sudoku which is valid.

Note:A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.


</br>

Solution

To determine whether a Sudoku is valid, we have to check every columns, every rows, every sub-block of the Sudoku only contains non-repeated number, that is to say, number from 0 to 9 only appears once.

To achieve this requirement, we can build a function to check isSubValid() to check whether certain part of the Sudoku has replicate number.

To check whether there is repeating numbers, we can use the features of Java HashSet, as HashSet cannot contain replicate numbers. When we try to add a number to the HashSet, if the set does not contain the target, then the add() function will return true. However, when there already exists the same number, the add() function will return false to indicate the replicate number.

In this way, for any columns, rows or blocks of Sudoku, we can implement this method to check whether this region has replicate number.
</br>
One more thing to make the code concise, instead of using another for-loop, we can use only one variable to represent all 9 blocks. We assign 9 blocks like following.

1  2  3
4  5  6
7  8  9

And in the first block, contains another 9 numbers,

[0][0]  [0][1]  [0][2]
[1][0]  [1][1]  [1][2]
[2][0]  [2][1]  [2][2]

By implementing

column_s    column_e    int row_s    int row_e
(i%3)*3     (i%3)*3+2   (i/3)*3      (i/3)*3+2)

we can iterate every elements in the block using just one variable i.
</br>
The code is shown as below.
Java

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        for(int i=0;i<9;i++){
        //Vertical
            if(!isSubValid(board,i,i,0,8))
                return false;
        //Horizontal
            if(!isSubValid(board,0,8,i,i))
                return false;
        //Block
            if(!isSubValid(board,(i%3)*3,(i%3)*3+2,(i/3)*3,(i/3)*3+2))
                return false;
        }
        return true;
    }
    
    private boolean isSubValid(char[][] board, int column_s, int column_e, int row_s, int row_e){
        Set set = new HashSet();
        int i = column_s;
        
        while(i<=column_e){
            int j = row_s;
            while(j<=row_e){
                if(board[i][j] != '.')
                    if(set.add(board[i][j]) == false)
                        return false;
                j++;
            }
            i++;
        }
        return true;
    }
}

</br>

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末浮还,一起剝皮案震驚了整個(gè)濱河市粥脚,隨后出現(xiàn)的幾起案子纲缓,更是在濱河造成了極大的恐慌叠穆,老刑警劉巖,帶你破解...
    沈念sama閱讀 219,427評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件谴供,死亡現(xiàn)場離奇詭異框喳,居然都是意外死亡唇兑,警方通過查閱死者的電腦和手機(jī)坎弯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,551評論 3 395
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人抠忘,你說我怎么就攤上這事撩炊。” “怎么了崎脉?”我有些...
    開封第一講書人閱讀 165,747評論 0 356
  • 文/不壞的土叔 我叫張陵拧咳,是天一觀的道長。 經(jīng)常有香客問我囚灼,道長骆膝,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,939評論 1 295
  • 正文 為了忘掉前任灶体,我火速辦了婚禮阅签,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘蝎抽。我一直安慰自己政钟,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,955評論 6 392
  • 文/花漫 我一把揭開白布樟结。 她就那樣靜靜地躺著养交,像睡著了一般。 火紅的嫁衣襯著肌膚如雪瓢宦。 梳的紋絲不亂的頭發(fā)上碎连,一...
    開封第一講書人閱讀 51,737評論 1 305
  • 那天,我揣著相機(jī)與錄音驮履,去河邊找鬼鱼辙。 笑死,一個(gè)胖子當(dāng)著我的面吹牛疲吸,可吹牛的內(nèi)容都是我干的座每。 我是一名探鬼主播,決...
    沈念sama閱讀 40,448評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼摘悴,長吁一口氣:“原來是場噩夢啊……” “哼峭梳!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起蹂喻,我...
    開封第一講書人閱讀 39,352評論 0 276
  • 序言:老撾萬榮一對情侶失蹤葱椭,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后口四,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體孵运,經(jīng)...
    沈念sama閱讀 45,834評論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,992評論 3 338
  • 正文 我和宋清朗相戀三年蔓彩,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了治笨。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片驳概。...
    茶點(diǎn)故事閱讀 40,133評論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖旷赖,靈堂內(nèi)的尸體忽然破棺而出顺又,到底是詐尸還是另有隱情,我是刑警寧澤等孵,帶...
    沈念sama閱讀 35,815評論 5 346
  • 正文 年R本政府宣布稚照,位于F島的核電站,受9級特大地震影響俯萌,放射性物質(zhì)發(fā)生泄漏果录。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,477評論 3 331
  • 文/蒙蒙 一咐熙、第九天 我趴在偏房一處隱蔽的房頂上張望弱恒。 院中可真熱鬧,春花似錦糖声、人聲如沸斤彼。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,022評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽琉苇。三九已至,卻和暖如春悦施,著一層夾襖步出監(jiān)牢的瞬間并扇,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,147評論 1 272
  • 我被黑心中介騙來泰國打工抡诞, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留穷蛹,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,398評論 3 373
  • 正文 我出身青樓昼汗,卻偏偏與公主長得像肴熏,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子顷窒,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,077評論 2 355

推薦閱讀更多精彩內(nèi)容