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

Solution: Using one loop

The idea is to use three 9x9 two-dimentional array to check each row, column, and sub board. We can iterate through every item on the board, and figure out which row and column it belongs to. To determine which sub-board it lies in, we need to do some calculation.

• Note: Remember to init array

    bool isValidSudoku(vector<vector<char>>& board) {
        int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};

        for(int i = 0; i < board.size(); ++i) {
            for(int j = 0; j < board[i].size(); ++j) {
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
                    if(used1[i][num] || used2[j][num] || used3[k][num])
                        return false;
                    used1[i][num] = used2[j][num] = used3[k][num] = 1;
                }
            }
        }

        return true;
    }

Solution: Using hash table

bool isValidSudoku(vector<vector<char>>& board) {
    // Check row
    for (int i=0; i<board.size(); i++) {
        unordered_map<int, bool> m;
        for (int j=0; j<board.size(); j++) {
            if (board[i][j] == '.') continue;

            if (m[board[i][j] - '0']) {
                return false;
            } else {
                m[board[i][j] - '0'] = true;
            }
        }
    }

    // Check column
    for (int i=0; i<board.size(); i++) {
        unordered_map<int, bool> m;
        for (int j=0; j<board.size(); j++) {
            if (board[j][i] == '.') continue;

            if (m[board[j][i] - '0']) {
                return false;
            } else {
                m[board[j][i] - '0'] = true;
            }
        }
    }

    // Check for sub board
    for (int i=0; i<board.size(); i++) {
        unordered_map<int, bool> m;
        for (int j=0; j<board.size(); j++) {
            int row = (i / 3) * 3 + j / 3;
            int col = (i % 3) * 3 + j % 3;
            if (board[row][col] == '.') continue;

            if (m[board[row][col] - '0']) {
                return false;
            } else {
                m[board[row][col] - '0'] = true;
            }
        }
    }

    return true;
}