Back to solutions

Valid Sudoku

MediumArrays

Check whether a partially filled 9x9 board has no rule violations.

Open problem
Constraints
  • Board is 9x9
  • cells are '1'-'9' or '.'

Track seen digits per unit

Time O(81) constantSpace O(81) constant

Maintain a 'seen' marker for each row, each column, and each 3x3 box. Scan every filled cell; compute its box index as (row/3)*3 + col/3. If the digit was already marked in its row, column, or box, the board is invalid; otherwise mark it in all three.

Key terms
box index:
Which 3x3 block a cell belongs to, computed from its row and column.
constraint set:
The collection of digits already used in a row, column, or box.
bool isValidSudoku(vector<string>& board) {
    bool rows[9][9] = {}, cols[9][9] = {}, box[9][9] = {};
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            char ch = board[r][c];
            if (ch == '.') continue;
            int d = ch - '1', b = (r / 3) * 3 + c / 3;
            if (rows[r][d] || cols[c][d] || box[b][d]) return false;
            rows[r][d] = cols[c][d] = box[b][d] = true;
        }
    return true;
}
Step by step
  1. Create seen structures for 9 rows, 9 columns, and 9 boxes.
  2. For each filled cell with digit d at (r, c), compute box b = (r/3)*3 + c/3.
  3. If d is already seen in row r, column c, or box b, return false.
  4. Otherwise mark d as seen in all three. Return true if no conflicts.