leetcode Question 121: Valid Sudoku

Valid Sudoku

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 '.'.


Analysis:
This question is so simple.
As the Sudoku has fixed size of board (9x9), the check procedure can be solved using just "for loop"
1. Check the rows and columns respectively, a mark array is used to check the numbers.
2. Check the 3x3 blocks, also using a mark array.


Code(updated 201309):

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<char, bool> row;
        map<char, bool> col;
        map<char, bool> block;
        
        for (int i=0;i<9;i++){
            col.clear();
            row.clear();
            for (int j=0;j<9;j++){
                if (board[i][j]!='.'){
                    if (col[board[i][j]]){
                        return false;
                    }else{
                        col[board[i][j]]=true;
                    } 
                }
                if (board[j][i]!='.'){
                    if (row[board[j][i]]){
                        return false;
                    }else{
                        row[board[j][i]]=true;
                    } 
                }
            }
        }
                
        for (int ii=0;ii<9;ii=ii+3){
            for (int jj=0;jj<9;jj=jj+3){
                block.clear();
                for (int i=ii;i<ii+3;i++){
                    for (int j=jj;j<jj+3;j++){
                        if (board[i][j]!='.'){
                            if (block[board[i][j]]){
                                return false;
                            }else{
                                block[board[i][j]]=true;
                            } 
                        }
                    }
                }        
            }
        }
        
        return true;
    }
};



Code(old version):

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
                
                
        //Check rows and columns        
        for (int i=0;i<9;i++){
            vector<bool>marki(10,false);
            vector<bool>markj(10,false);
            for (int j=0;j<9;j++){
                if (board[i][j]!='.'){
                    if (marki[int(board[i][j]-'0')]==false){marki[int(board[i][j]-'0')]=true;}
                    else {return false;}
                }
                if (board[j][i]!='.'){
                    if (markj[int(board[j][i]-'0')]==false){markj[int(board[j][i]-'0')]=true;}
                    else {return false;}
                }
            }
        }
            
        //Check 3x3 blocks
        for (int i=0;i<9;i+=3){
            for (int j=0;j<9;j+=3){
                vector<bool>mark(10,false);
                for (int p=0;p<3;p++){
                    for (int q=0;q<3;q++){
                        if (board[i+p][j+q]!='.'){
                           if (mark[int(board[i+p][j+q]-'0')]==false) {mark[int(board[i+p][j+q]-'0')]=true;}
                            else {return false;}
                        }        
                    }
                }
                
                
            }
        }
        return true;
        
    }
};

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete