康瑞部落

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

A partially filled sudoku which is valid.

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

解题思路：

题意为验证数独的有效性。这里说的有效是值谜面的有效性，不包括是否能够解出。数独的规则是，每一行1-9只出现一次，每一列1-9只出现一次，每一个小九宫格1-9只出现一次。依次验证即可。一个陷阱就是字符减的不是'0'，而是'1'

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //验证每一行是否有效
        for(int i=0; i<9; i++){
            if(!checkRowValid(board, i)){
                return false;
            }
        }
        //验证每一列是否有效
        for(int i=0; i<9; i++){
            if(!checkColumnValid(board, i)){
                return false;
            }
        }
        //验证每一格是否有效
        for(int i=0; i<9; i=i+3){
            for(int j=0; j<9; j=j+3){
                if(!checkGridValid(board, i, j)){
                    return false;
                }
            }
        }
        return true;
    }
    
    //验证每个格是否有效，传入的是左上角的下标
    bool checkGridValid(vector<vector<char>>& board, int m, int n){
        bool flag[9];
        memset(flag, 0, sizeof(bool)*9);
        for(int i=m; i<m+3; i++){
            for(int j=n; j<n+3; j++){
                if(board[i][j]=='.'){
                    continue;
                }
                if(flag[board[i][j]-'1']){
                    return false;
                }
                flag[board[i][j]-'1']=true;
            }
        }
        return true;
    }
    
    //验证每一行是否有效，传入的是行号
    bool checkRowValid(vector<vector<char>>& board, int m){
        bool flag[9];
        memset(flag, 0, sizeof(bool)*9);
        for(int i=0; i<9; i++){
            if(board[m][i]=='.'){
                continue;
            }
            if(flag[board[m][i]-'1']){
                return false;
            }
            flag[board[m][i]-'1']=true;
        }
        return true;
    }
    
    //验证每一列是否有效，传入的是列号
    bool checkColumnValid(vector<vector<char>>& board, int n){
        bool flag[9];
        memset(flag, 0, sizeof(bool)*9);
        for(int i=0; i<9; i++){
            if(board[i][n]=='.'){
                continue;
            }
            if(flag[board[i][n]-'1']){
                return false;
            }
            flag[board[i][n]-'1']=true;
        }
        return true;
    }
};

二次刷题(2015-07-31)

难点在于宫的判断。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //验证每一行是否正确
        for(int i=0; i<9; i++){
            vector<bool> flag(9, false);
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'){
                    if(flag[board[i][j]-'1']){
                        return false;
                    }else{
                        flag[board[i][j]-'1'] = true;
                    }
                }
            }
        }
        
        //验证每一列是否正确
        for(int i=0; i<9; i++){
            vector<bool> flag(9, false);
            for(int j=0; j<9; j++){
                if(board[j][i]!='.'){
                    if(flag[board[j][i]-'1']){
                        return false;
                    }else{
                        flag[board[j][i]-'1'] = true;
                    }
                }
            }
        }
        
        //验证每一宫是否正确，这里难点在于每一宫的下标对应关系
        for(int i=0; i<9; i=i+3){
            for(int j=0; j<9; j=j+3){
                vector<bool> flag(9, false);
                for(int x = i; x<i+3; x++){
                    for(int y=j; y<j+3; y++){
                        if(board[x][y]!='.'){
                            if(flag[board[x][y]-'1']){
                                return false;
                            }else{
                                flag[board[x][y]-'1'] = true;
                            }
                        }
                    }
                }
            }
        }
        return true;
    }
};