Marauder Bot

Problem

You are given a partially filled 9x9 Sudoku board. Determine whether the placed digits obey Sudoku's rules: no digit from 1 through 9 repeats within any row, column, or 3x3 box. Empty cells are ignored; the task is only to validate current placements, not to solve the puzzle.

Example. A board where the digit 5 appears twice in the same row is invalid. A board where every filled digit is unique within its own row, column, and box is valid, even if many cells remain empty.

Key idea

Re-scanning the relevant row, column, and box for every filled cell works but repeats a lot of comparisons. A cleaner approach makes one pass over all 81 cells, maintaining for each of the 9 rows, 9 columns, and 9 boxes a record of which digits have been seen so far, such as a small set.

For each filled cell, compute its row, column, and box index: the box index comes from dividing row and column by 3, with integer division, and combining the two into an index from 0 to 8. Check whether the digit is already recorded for that row, column, or box; if so, the board is invalid. Otherwise mark it seen in all three trackers and continue. Finishing without a collision means the board is valid.

Solution

function isValidSudoku(board: string[][]): boolean {
  const rows: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const cols: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const boxes: Set<string>[] = Array.from({ length: 9 }, () => new Set());

  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      const digit = board[row][col];
      if (digit === '.') {
        continue;
      }

      const box = Math.floor(row / 3) * 3 + Math.floor(col / 3); // maps row/col to one of the nine 3x3 boxes
      if (rows[row].has(digit) || cols[col].has(digit) || boxes[box].has(digit)) {
        return false; // digit already seen in this row, column, or box
      }

      rows[row].add(digit);
      cols[col].add(digit);
      boxes[box].add(digit);
    }
  }

  return true;
}

Complexity

Time: O(1) for the fixed 9x9 board, since it always has 81 cells; more generally, O(n²) for an n x n board, one visit per cell.
Space: O(1) for the fixed board, since the number of trackers is constant; O(n) in the general case.

Watch out for

The box-index formula is the easiest part to get wrong; confirm row and column are each divided by 3 before combining into one of the nine box indices.
Empty cells must be skipped rather than treated as a digit needing validation.
The problem does not ask whether the board is solvable, only whether the filled cells currently violate a rule.

Pattern

This is "three overlapping groupings, one seen-set each": every element belongs to several scopes at once, and each scope gets its own tracker. The same idea generalizes to constraint-checking problems where a value must be validated against multiple independent groupings simultaneously.

Valid Sudoku