---
# System prepended metadata

title: "\n    Leetcode 36. Valid Sudoku\n"
tags: [Hash Table]

---

###### tags: `Hash Table`
<h1>
    Leetcode 36. Valid Sudoku
</h1>
<ol>
    <li>問題描述</li>
    Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

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

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.<br>
    
Example 1:
    
    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.
    
<li>Input的限制</li>
    <ul>
        <li>board.length == 9</li>
        <li>board[i].length == 9</li>
        <li>board[i][j] is a digit 1-9 or '.'.</li>
    </ul>
    <br>

<li>思考流程</li>
    <ul>
        <li>Hash Set</li>
        數獨的規則是每列的數字不能重複、每行的數字不能重複、每個小 3x3 宮格內的數字不能重複。假設數獨板是一個 9 x 9 的大小，這意味著，我們必須準備 27 個容器來檢查這些數字有沒有重複。然後，我們從左上方開始遍歷數獨板內的每一個數字，檢查它在所在的 row, column, and block 內是否已經有出現過，若有 return False，否則就將此數字加入到所屬的 row, column, block 內。檢查完數獨板內所有數字皆合法，就 return True。
        <br>
        <br>
        因為 input board 的限制是 9x9 的大小，所以 time complexity 和 space complexity 皆是 O(1)。但如果我們假設數獨板的長度為 n，其 block 的格子數也是為 n，則因為要掃過數獨板的每一個數字，則 time complexity 為 O(n^2)。而我們會準備 3 個數獨板大小的空間來記錄這些數字的出現，故 space complexity 為 O(n^2)。
        <br>
        <br>
        Time Complexity: O(n^2); Space Complexity: O(n^2)
        <br>
        <br>
        <li>Bitmasking</li>
        Bitmasking 作法概念其實與 hash set 差別不大，只是 hash set 最差會準備 3 * N^2 個 space 來儲存數字是否出現在各自的 row, col, and block；而 bitmasking 則是準備了 3 * N 個整數來儲存數字的狀態。<br><br>
        一樣 bitmasking 需要把數獨板的每個數字掃過一遍，在檢查是否出現過的時候，索引 0 ~ N-1 對應到數字 1 ~ N，我們計算出該數字應該對應的 bit 位置，對儲存整數進行 bitwise and 操作( 只有需要檢查的數字之 bit 為 1，其他 bits 皆為 0 )，若該數字已經出現過，則 return False；若未出現過則對該整數進行 bitwise or 操作，將其記錄起來。對 row, column, and block 都檢查過後，即可換下一個數字。
        <br>
        <br>
        Time Complexity: O(n^2); Space Complexity: O(n)
        <br>
        <br>
    </ul>
<li>測試</li>
    <ul>
        <li>Invalid element in board( edge case )</li>
        如果數獨板內出現非"." and 1~9 的字元，則必須回報錯誤 input board 訊息。
</ol>