###### tags: `Leetcode` `medium` `hash` `python`

# 36. Valid Sudoku

## [題目連結:] https://leetcode.com/problems/valid-sudoku/

## 題目:
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.


Input: board = 
[["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"]]
Output: true

**Example 2:**

Input: board = 
[["8","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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

#### [圖片來源:] https://leetcode.com/problems/valid-sudoku/

## 解題想法:
* 題目為要求檢查棋盤:
* 每行能填1~9 且其中數字不能重複
* 每列能填1~9 且其中數字不能重複
* 每個3 * 3九宮格，能填1~9且其中數字不能重複

* 想法:
* 分別將row、col、grid創建字典
* key:當前編號
* val:list，存出現過的數字
* 判斷當前board[i][j]:
* 若遇到'.'
* continue
* 看row是否有重複的:
* 若有: False
* 否則: row[i].append(board[i][j])
* 看col是否有重複的:
* 若有: Fasle
* 否則: col[j].append(board[i][j])
* 判斷格有沒有遇到重複的:
* 技巧!!! **格的編號**
* 用row當十位，col當個位
* (row//3)*10+col//3

        grid編號:
         00 01 02
         10 11 12
         20 21 22

## Python:

from collections import defaultdict

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row = defaultdict(list)
        col = defaultdict(list)
        grid = defaultdict(list)
        for i in range(0,9):
            for j in range(0,9):
                if board[i][j]=='.':
                    continue
                #看row有沒有遇到重複的
                if board[i][j] in row[i]:
                    return False
                else:
                    row[i].append(board[i][j])
                #看col有沒有遇到重複的:
                if board[i][j] in col[j]:
                    return False
                else:
                    col[j].append(board[i][j])
                #看格有沒有遇到重複的:
                #grid編號 可以用(row//3)*10+col//3 
                # 00 01 02
                # 10 11 12
                # 20 21 22
                if board[i][j] in grid[(i//3)*10+j//3]:
                    return False
                else:
                    grid[(i//3)*10+j//3].append(board[i][j])
        #print(row,col,grid)
        return True

if __name__ == '__main__':
    result = Solution()
    board = [["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"]]
    ans = result.isValidSudoku(board)
    print(ans)