Validate Sudoku

LeetCode #36

Description:

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

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

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Example:

Note

Idea:

1. 检查每一行
2. 检查每一列
3. 检查每一个block

如果都OK，return true。每一步不ok，return false。

Code:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int N = 9;
        vector<bool> digit_used(N, false);


        for(int i=0; i<N; ++i){
            // check rows
            fill(digit_used.begin(), digit_used.end(), false);
            for(int j=0; j<N; ++j){
                if(board[i][j]!='.'){
                    if(digit_used[board[i][j]-'1']==true){
                        return false;
                    }
                    digit_used[board[i][j]-'1']=true;
                }
            }
            // check columns
            fill(digit_used.begin(), digit_used.end(), false);
            for(int j=0; j<N; ++j){
                if(board[j][i]!='.'){
                    if(digit_used[board[j][i]-'1']==true){
                        return false;
                    }
                    digit_used[board[j][i]-'1']=true;
                }
            }
        }

        int M=3;
        for(int block_i=0; block_i<M; block_i++){
            for(int block_j=0; block_j<M; block_j++){
                // check blocks
                fill(digit_used.begin(), digit_used.end(), false);
                for(int local_i=0; local_i<M; local_i++){
                    for(int local_j=0; local_j<M; local_j++){
                        int global_i=block_i*M+local_i;
                        int global_j=block_j*M+local_j;
                        if(board[global_i][global_j]!='.'){
                            if(digit_used[board[global_i][global_j]-'1']==true){
                                return false;
                            }
                            digit_used[board[global_i][global_j]-'1']=true;
                        }
                    }
                }

            }
        }

        return true;
    }
};