# 36. Valid Sudoku
###### tags: `leetcode` `36` `medium`

## :memo: Question
Determine if a ```9 x 9``` Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits ```1-9``` without repetition.
Each column must contain the digits ```1-9``` without repetition.
Each of the nine ```3 x 3``` sub-boxes of the grid must contain the digits ```1-9``` without repetition.

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

## :memo: 題意
* 就是給你 9*9 的數獨矩陣，讓你判斷這是不是有效的數獨，note 有提醒你你只要去判斷他給你的矩陣是有數字的就好，空格的就不用去管他。

## :memo: My first solution
* :medal: **思考一**: 這題我一開始的想法就是用 dictionary 去判斷每行每列以及每個3*3的九宮格是否有重複的數字，有重複的就 return False 沒有就將值塞到 dictionary。暴力 for loop ，因為我想不到有更好的解法。

## :memo: Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        x = len(board)
        y = len(board[0])
        
        for i in range(x):
            dicx = {} 
            for j in range(y):
                if board[i][j].isdigit():
                    if board[i][j] not in dicx:
                        dicx[board[i][j]]  = True
                    else:
                        return False
        
        for i in range(y):
            dicx = {}
            for j in range(x):
                if board[j][i].isdigit():
                    if board[j][i] not in dicx:
                        dicx[board[j][i]]  = True
                    else:
                        return False
                    
        zz = [[0,0],[0,3],[0,6],[3,0],[3,3],[3,6],[6,0],[6,3],[6,6]]

        for a,b in zz:
            dicx = {}
            for i in range(3):    
                for j in range(3):
                    if board[a+i][b+j].isdigit():
                        if board[a+i][b+j] not in dicx:
                            dicx[board[a+i][b+j]]  = True
                        else:
                            return False

:bulb: **檢討**: 程式真的寫得蠻醜的，然後是非常暴力的寫法，檢驗 3 * 3 方格這麼想了比較久要怎麼寫，應該要是可以合再一起寫的，但我覺得如果我是第一次遇到這題目，我面試應該寫不出來，所以直接硬寫一個很醜的答案，最後submit有過，沒有 time out。
這個時間複雜度就是 9 * 9 * 3。

## :memo: 別人的漂亮寫法 Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for i in range(9)]
        cols = [set() for i in range(9)]
        mMat = [set() for i in range(9)]
        
        for i in range(9):
            for j in range(9):
                cur = board[i][j]
                if cur != '.':
                    
                    k = (i // 3 ) * 3 + j // 3
                
                    if cur not in rows[i]: rows[i].add(cur)
                    else: return False
                    
                    if cur not in cols[j]: cols[j].add(cur)
                    else: return False
                
                    if cur not in mMat[k]: mMat[k].add(cur)
                    else: return False
        return True

:bulb: **討論**: 這種寫法漂亮很多時間複雜度也下降，只要 9 * 9。

## :memo: bigO
* 時間複雜度: O(9 * 9)
* 空間複雜度: O(9 * 9 * 9)，最差的情況，input 給你解完的數獨，所以每個set都塞好塞滿