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

  • A Sudoku board is valid if there exists no duplicates for every row, column, and 3x3 square. That is all I am checking for.

bool scan3x3(vector<vector<char>>& board, int r_start, int c_start) {
    unordered_set<int> nums;
    for (int i = r_start; i < r_start + 3; i++) {
        for (int j = c_start; j < c_start + 3; j++) {
            if (board.at(i).at(j) == '.') {
                continue;
            }
            //cout << board.at(i).at(j) << " ";
            auto found = nums.find(board.at(i).at(j));
            if (found == nums.end()) {
                // not found
                nums.insert(board.at(i).at(j));
            }
            else {
                return false;
            }
        }
        //cout << endl;
    }
    return true;
}

bool isValidSudoku(vector<vector<char>>& board) {
    unordered_set<char> nums;

    // scan every row
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board.at(i).size(); j++) {
            if (board.at(i).at(j) == '.') {
                continue;
            }
            auto found = nums.find(board.at(i).at(j));
            if (found == nums.end()) {
                // not found
                nums.insert(board.at(i).at(j));
            }
            else {
                return false;
            }
        }
        nums.clear();
    }

    // scan every column
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board.at(i).size(); j++) {
            if (board.at(j).at(i) == '.') {
                continue;
            }
            auto found = nums.find(board.at(j).at(i));
            if (found == nums.end()) {
                // not found
                nums.insert(board.at(j).at(i));
            }
            else {
                return false;
            }
        }
        nums.clear();
    }

    // scan every 3x3
    for (int i = 0; i <= 6; i += 3) {
        for (int j = 0; j <= 6; j += 3) {
            if (scan3x3(board, i, j) == false) {
                return false;
            }
            //pause();
        }
    }

    return true;
}

Last updated