LeetCode题目:Valid Sudoku

By | 2012 年 11 月 7 日

神奇了,只检查了每行重复、每列重复和每9宫格重复就过了大测试集合。
难道只要满足每行、每列、每9宫格不重复的数独都有解?



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 ‘.’.
sudoku
A partially filled sudoku which is valid.



代码:28ms过大集合

class Solution {
public:
    bool isValidSudoku(vector > &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = board.size();
        if(9 != rows) return false;
        int cols = board[0].size();
        if(9 != cols) return false;
        //1.check duplications in each row
        int dup[10];//hash for 1 to 9
        for(int ir = 0; ir < rows; ++ir) {
            for(int i = 0; i <= 9; ++i)
                dup[i] = 0;
            for(int i = 0; i < 9; ++i){
                char c = board[ir][i];
                if(c == '.')
                    ++dup[0];
                else {
                    int hash = c - '0';
                    if(dup[hash] == 1) {
                        return false;
                    } else {
                        ++dup[hash];
                    }
                }
            }
        }
        //2. check duplications in each cols
        for(int ic = 0; ic < cols; ++ic) {
            for(int i = 0; i <= 9; ++i)
                dup[i] = 0;
            for(int i = 0; i < 9; ++i){
                char c = board[i][ic];
                if(c == '.')
                    ++dup[0];
                else {
                    int hash = c - '0';
                    if(dup[hash] == 1) {
                        return false;
                    } else {
                        ++dup[hash];
                    }
                }
            }
        }
        //3. check duplications in each 3 * 3 grid
        for(int ir = 0; ir < rows; ir += 3) {
            for(int ic = 0; ic < cols; ic += 3) {
                for(int i = 0; i <= 9; ++i)
                    dup[i] = 0;
                for(int iir = 0; iir < 3; ++iir) {
                    for(int iic = 0; iic < 3; ++iic) {
                        char c = board[ir + iir][ic + iic];
                        if(c == '.')
                            ++dup[0];
                        else {
                            int hash = c - '0';
                            if(dup[hash] == 1) {
                                return false;
                            } else {
                                ++dup[hash];
                            }
                        }
                    }
                }
            }
        }
        return true;
    }
};

2 thoughts on “LeetCode题目:Valid Sudoku

  1. kimi

    题目最后说
    A valid Sudoku board (partially filled) is not necessarily solvable.
    并不是满足这里的“合法”数独就有解

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注