# 【LeetCode】 36. Valid Sudoku

## Description
> Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

> The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

> 判斷一個9x9的數獨是否符合規則。有被填入數字的格子必須遵守以下規則：
> - 每一排都包含1-9的數字，且不能重複。
> - 每一列都包含1-9的數字，且不能重複。
> - 每一個3x3的小格子都都包含1-9的數字，且不能重複。

> 數獨板只有部分會被填入，空的格子會用字元'.'表示。

## Example:

Example 1:

Input:
[
  ["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:
[
  ["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.

## Solution

* 單純照規則跑迴圈判斷即可，一開始可以寫成三段，分別去跑排、列、格。寫完之後會發現For Loop的部分可以合併，增加速度。
* 比較需要思考的是`3*3`的小格子要怎麼寫index。

### Code

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            bool rows[9]={false};
            bool cols[9]={false};
            bool blocks[9]={false};
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    if(rows[board[i][j]-'1'])
                        return false;
                    rows[board[i][j]-'1']=true;
                }
                if(board[j][i]!='.')
                {
                    if(cols[board[j][i]-'1'])
                        return false;
                    cols[board[j][i]-'1']=true;
                }
                    
                if(board[((i/3)*3 + j/3)][((i%3)*3) + j%3]!='.')
                {
                    if(blocks[board[((i/3)*3 + j/3)][((i%3)*3) + j%3]-'1'])
                        return false;
                    blocks[board[((i/3)*3 + j/3)][((i%3)*3) + j%3]-'1']=true;
                }
            }
        }
        return true;
    }
};

###### tags: `LeetCode` `C++`