【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++