# Approach 1: Naive — DO NOT use in interview (too verbose)
def isValidSudoku_naive(board):
    # Check rows
    for row in board:
        seen = set()
        for c in row:
            if c == '.': continue
            if c in seen: return False
            seen.add(c)
    
    # Check cols (transpose and repeat)
    for col in range(9):
        seen = set()
        for row in range(9):
            c = board[row][col]
            if c == '.': continue
            if c in seen: return False
            seen.add(c)
    
    # Check 3x3 boxes
    for box_row in range(3):
        for box_col in range(3):
            seen = set()
            for r in range(box_row*3, box_row*3+3):
                for c in range(box_col*3, box_col*3+3):
                    val = board[r][c]
                    if val == '.': continue
                    if val in seen: return False
                    seen.add(val)
    return True
# Time: O(81) = O(1) technically since board is fixed 9x9
# Space: O(9) per iteration
# Problem: 3 separate passes, harder to extend, verbose

from collections import defaultdict

def isValidSudoku(board):
    # Three dictionaries: rows, columns, boxes
    # Each maps an index to a set of seen digits
    rows = defaultdict(set)   # rows[r] = {digits seen in row r}
    cols = defaultdict(set)   # cols[c] = {digits seen in col c}
    boxes = defaultdict(set)  # boxes[(r//3, c//3)] = {digits seen in box}

    for r in range(9):
        for c in range(9):
            val = board[r][c]
            
            # Skip empty cells
            if val == '.':
                continue
            
            # Calculate box index — THE KEY TRICK
            box_key = (r // 3, c // 3)
            
            # Check all three constraints simultaneously
            if (val in rows[r] or
                val in cols[c] or
                val in boxes[box_key]):
                return False  # Duplicate found — invalid!
            
            # Add to all three tracking sets
            rows[r].add(val)
            cols[c].add(val)
            boxes[box_key].add(val)
    
    return True  # No violations found

Board (first 3 rows shown):
["5","3",".",  ".","7",".",  ".",".","."]
["6",".",  ".",  "1","9","5",  ".",".","."]
[".","9","8",  ".",".",  ".",  ".","6","."]

board = [['.']*9 for _ in range(9)]
# Result: True — empty board is valid
# Our code handles this: all '.' cells are skipped

# Trap: this is invalid even though row 0 and col 3 look different
# '5' at (0,0) and '5' at (2,2) — same 3×3 box!
# The box_key trick catches this: both map to (0,0)

# Each row and column could be valid individually,
# but a 3×3 box might have duplicates
# Always check all THREE constraints — don't shortcut!

In databases, a UNIQUE constraint across multiple columns is the same idea:
  UNIQUE(user_id, date) — same as "no two rows share both values"
  
PostgreSQL internally uses hash indexes (like our sets) per constraint.

Google Sheets "no duplicates in range" validation:
  Checks each row, column, named range simultaneously
  Exact same three-constraint structure

// Same pattern: check uniqueness across multiple dimensions
const seen = { byEmail: new Set(), byUsername: new Set() };
users.forEach(user => {
  if (seen.byEmail.has(user.email)) throw Error("duplicate email");
  seen.byEmail.add(user.email);
});

不完全能，但可以压缩。/ Not quite, but you can compress.

You could encode sets as bitmasks (bit 1 = digit 1 seen, bit 2 = digit 2, etc.):
  rows = [0] * 9   # 9 integers, each bit i = digit i+1 seen
  cols = [0] * 9
  boxes = [0] * 9

  For digit d (1-9), check: if rows[r] & (1 << d): return False
                            rows[r] |= (1 << d)

Space: O(27 integers) = O(1). Faster in practice due to cache locality.

# Same code, parameterized:
def isValidSudokuNxN(board, n=9, box_size=3):
    rows = defaultdict(set)
    cols = defaultdict(set)
    boxes = defaultdict(set)
    for r in range(n):
        for c in range(n):
            val = board[r][c]
            if val == '.': continue
            box_key = (r // box_size, c // box_size)
            if val in rows[r] or val in cols[c] or val in boxes[box_key]:
                return False
            rows[r].add(val); cols[c].add(val); boxes[box_key].add(val)
    return True
# For 16×16: n=16, box_size=4 → same logic, bigger constants

验证是求解的子问题。/ Validation is a sub-problem of solving.

Solving requires backtracking:
1. Find an empty cell
2. Try digits 1-9
3. For each digit: call isValid (our function!) to check constraints
4. If valid, place digit, recurse
5. If recursion fails, backtrack (remove digit, try next)

Time: O(9^m) where m = number of empty cells — exponential worst case
Typical Sudoku (m~50 empty cells) solves in milliseconds due to pruning.