Valid Sudoku

Given a 9x9 Sudoku board, determine if it is valid. The board is valid if:

• Each row contains no duplicate digits (1-9).
• Each column contains no duplicate digits.
• Each 3x3 sub-box contains no duplicate digits.

Empty cells are represented by '.'. You only need to validate the current state, not solve the puzzle.

Why this is worth learning

Validation is three simultaneous uniqueness checks. A board can satisfy these checks without being solvable; this function does not search for a completion.

Before coding: one-minute experiment

Cells (0,0) and (1,1) both contain 7; all other cells are empty. Which rule fails?

Function signature

func IsValidSudoku(board [][]byte) bool

Inputs / outputs

• board: 9x9 grid of bytes ('1'-'9' or '.').
• Return: true if the board is valid.

Example

5........
.5.......
.........
.........
.........
.........
.........
.........
.........

Output: false

Each text row represents one nine-byte slice. The two 5s are in distinct rows and columns, but both occupy the top-left 3×3 box.

Constraints

• len(board) == 9, len(board[i]) == 9
• board[i][j] is '.' or '1'..'9'

Core idea (near-solution)

Track seen digits for each row, column, and 3x3 box. If a digit repeats in any set, the board is invalid.

Invariant: after processing cell (r,c), all seen sets correctly represent digits encountered so far.

Algorithm (step-by-step)

1. Create 9 row sets, 9 column sets, and 9 box sets (or bitmasks).
2. For each cell (r,c):
   • If the cell is '.', continue.
   • Map the digit to an index 0-8.
   • Compute box index: (r/3)*3 + (c/3).
   • If the digit is already in the row/col/box set, return false.
   • Otherwise record it.
3. If all cells pass, return true.

Correctness sketch

For every processed nonempty cell, its digit bit is present in exactly the associated row, column, and box masks. Before inserting the next digit, a set bit in any corresponding mask witnesses an earlier equal digit in that unit and therefore a violation. If all three bits are absent, adding them preserves uniqueness in every processed unit. The box index (r/3)*3+c/3 identifies each of the nine disjoint 3-by-3 boxes. After 81 cells, every possible row, column, or box duplicate would have been detected when its second occurrence was processed; absence of a detection is exactly current-state validity.

Trace (hand walkthrough)

Use the board from the example.
- (0,0) contains '5': digit index 4, bit=16, box=(0/3)*3+0/3=0
- rows[0], cols[0], boxes[0] are initially 0; set bit 16 in all three
- skip dots without changing any mask
- (1,1) contains '5': its row and column masks are empty
- boxes[0]&16 is nonzero, so reject the repeated digit in box 0

A row-only or column-only validator would incorrectly accept this board.

Pitfalls to avoid

• Incorrect box index calculation.
• Forgetting that '.' should be ignored.

Debugging lens

Test row-only, column-only, and box-only duplicates separately. Dots never set a digit bit. A fixed 9-by-9 input has constant work; do not describe it as a solver.

Complexity

• Time: O(1) (fixed 9x9 board).
• Extra space: O(1).

Implementation notes (Go)

• Bitmasks are compact: use 9-element int arrays for rows/cols/boxes.

Reconstruction checkpoint

Cells (0,0) and (1,1) both contain 7; all other cells are empty. Which rule fails?

Return to Matrix · Module quiz