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.

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

board = [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  ...
]
Output: true

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

• Invariant: after processing cell (r,c), all seen sets correctly represent digits encountered so far.
• Boundary/marker invariants ensure each cell is processed correctly.
• In-place encodings preserve original state until updates are finalized.
• Thus the final matrix matches the required transformation.

Trace (hand walkthrough)

Example input:
board = [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  ...
]
Output: true

Walk:
- row 0 sees {5,3,7} -> no duplicates
- col 0 sees {5,6} -> no duplicates
- box (rows0-2, cols0-2) sees {5,3,6,9,8} -> no duplicates
- all filled cells pass row/col/box checks -> true

Pitfalls to avoid

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

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.