# 36 - Valid Sudoku

解法一 - 暴力法

最直觀的解法就是

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bitset<9> check;

        // Check each row
        for(int row=0; row<board.size(); row++) {
            // reset bitset to all 0
            check.reset();

            for(int col=0; col<9; col++) {
                if(board[row][col] == '.') 
                    continue;
                else{
                    if(check.test(board[row][col] - '1')) {
                        return false;
                    }
                    else {
                        check.set(board[row][col] - '1');
                    }
                }
            }
        }

        // Check each column
        for(int col=0; col<9; col++) {
            // reset bitset to all 0
            check.reset();

            for(int row=0; row<9; row++) {
                if(board[row][col] == '.') 
                    continue;
                else{
                    if(check.test(board[row][col] - '1')) {
                        return false;
                    }
                    else {
                        check.set(board[row][col] - '1');
                    }
                }
            }
        }

        // Check each 3x3 block
        for(int row=0; row<board.size(); row+=3) {
            for(int col=0; col<9; col+=3) {
                // reset bitset to all 0
                check.reset();

                // iterate through 3x3 block
                for(int i=0; i<3; i++) {
                    for(int j=0; j<3; j++) {
                        if(board[row+i][col+j] == '.') 
                            continue;
                        else{
                            if(check.test(board[row+i][col+j] - '1')) {
                                return false;
                            }
                            else {
                                check.set(board[row+i][col+j] - '1');
                            }
                        }
                    }
                }
            }
        }

        return true;
    }
};

// idea: go through each row/column/3x3 block and count the number, if one number appears more than 1 time, then return false

這樣解的效率有點差，因為會需要 go through 整個 matrix 三次，雖然跑起來的結果看起來還可以：

Runtime: 8 ms, faster than 99.49% of C++ online submissions for Valid Sudoku. Memory Usage: 9.5 MB, less than 72.81% of C++ online submissions for Valid Sudoku.

解法二 - 多用一些空間來提升時間效率

我們也可以用三個 Hash Table，分別儲存每個 row, column 跟 box 的數字出現次數，只要一超過 1 就 return false。程式碼實作如下：