Valid Sudoku

http://www.lintcode.com/en/problem/valid-sudoku/

Solution

简单。判断每一行，每一列，每一个3x3的方格都valid就可以了。可以用一个hash快速查找。

class Solution {
public:
    /**
      * @param board: the board
      * @return: wether the Sudoku is valid
      */
    bool isValidSudoku(const vector<vector<char>>& board) {
        int m = board.size();
        if(m != 9) return false;
        int n = board[0].size();
        if(n != 9) return false;

        //valid numbers
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                if(board[i][j] != '.' &&(board[i][j] > '9' || board[i][j] < '1')) {
                    return false;
                }
            }
        }
        //valid rows
        for(int i=0; i<9; i++) {
            unordered_map<char, int> map;
            for(int j=0; j<9; j++) {
                if(board[i][j] == '.') {
                   continue;
                }
                if(map.find(board[i][j]) != map.end()) {
                    return false;
                }
                map[board[i][j]] = j;
            }
        }
        //valid dolumns
        for(int j=0; j<9; j++) {
            unordered_map<char, int> map;
            for(int i=0; i<9; i++) {
                if(board[i][j] == '.') {
                   continue;
                }
                if(map.find(board[i][j]) != map.end()) {
                    return false;
                }
                map[board[i][j]] = i;
            }
        }
        //valid 3x3 quads
        for(int m=0; m<3; m++) {
            for(int n=0; n<3; n++) {
               unordered_map<char, int> map; 
               for(int i=m*3; i<3*m+3; i++) {
                    for(int j=n*3; j<n*3+3; j++) {
                        if(board[i][j] == '.') {
                           continue;
                        }
                        if(map.find(board[i][j]) != map.end()) {
                            return false;
                        }
                        map[board[i][j]] = j;
                    }
                }
            }
        }
        return true;

    }
};

也可以用一个bool used[9]数组保存对应数字是不是出现过，更简单。

// Time:  O(9^2)
// Space: O(9)

class Solution {
public:
    /**
     * @param board: the board
     * @return: wether the Sudoku is valid
     */
    bool isValidSudoku(const vector<vector<char>>& board) {
        // Check row constraints.
        for (int i = 0; i < board.size(); ++i) {
            if (HasDuplicate(board, i, i + 1, 0, board.size(), board.size())) {
                return false;
            }
        }

        // Check column constraints.
        for (int j = 0; j < board.size(); ++j) {
            if (HasDuplicate(board, 0, board.size(), j, j + 1, board.size())) {
                return false;
            }
        }

        // Check region constraints.
        int region_size = sqrt(board.size());
        for (int i = 0; i < region_size; ++i) {
            for (int j = 0; j < region_size; ++j) {
                if (HasDuplicate(board, region_size * i, region_size * (i + 1),
                                 region_size * j, region_size * (j + 1), board.size())) {
                    return false;
                }
            }
        }
        return true;
    }

    // Return true if subarray board[start_row : end_row - 1][start_col : end_col - 1]
    // contains any duplicates in [1 : num_elements]; otherwise return false.
    bool HasDuplicate(const vector<vector<char>>& board, int start_row, int end_row,
                      int start_col, int end_col, int num_elements) {
        deque<bool> is_present(num_elements + 1, false);
        for (int i = start_row; i < end_row; ++i) {
            for (int j = start_col; j < end_col; ++j) {
                if (board[i][j] != '.' && is_present[board[i][j] - '0']) {
                    return true;
                }
                is_present[board[i][j] - '0'] = true;
            }
        }
        return false;
    }
};