Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes must contain the digits 1-9 without repetition.

Note: We are NOT solving Sudoku. Just validating the current board. Empty cells are represented by '.'.

Examples

Example 1:

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

Example 2:

Input: board = (same as above but with board[0][0] changed to "8")
Output: false
Explanation: Two 8's in the top-left 3x3 sub-box.

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'

Thinking Process

Fixed size 9x9 – maximum 81 cells, so time complexity is essentially constant. This problem is not about performance; it’s about clean constraint modeling.

We need to detect duplicates across 27 constraint groups:

  • 9 rows
  • 9 columns
  • 9 sub-boxes (3x3 blocks)

Why Bitmask?

Instead of using set or unordered_set, use an integer bitmask per group:

  • Faster – no hash overhead
  • Cleaner – single integer per group
  • Classic bit manipulation trick

Encoding

For digit d (character '1' to '9'):

num = d - '1'       // 0..8
mask = 1 << num     // one-hot bit

Each row/col/box maintains an integer. If the bit is already set, we found a duplicate.

Box Index: Why (i/3)*3 + (j/3) Works

The 9 sub-boxes are indexed as:

0 1 2
3 4 5
6 7 8
  • (i / 3) gives the block row (0, 1, or 2)
  • (j / 3) gives the block column (0, 1, or 2)
  • Combined: (i / 3) * 3 + (j / 3) maps to 0..8

Common wrong formula: (i % 3) * 3 + (j % 3) – this gives position within a box, not the box index.

Bit manipulation 1 0 1 1 0 1 0 XOR pairs · masks · shifts

Approach

Single pass over all 81 cells. For each filled cell:

  1. Compute num = board[i][j] - '1' and mask = 1 << num
  2. Compute boxIndex = (i / 3) * 3 + (j / 3)
  3. Check if mask already exists in row[i], col[j], or box[boxIndex]
  4. If yes, return false. Otherwise, set the bit.

Time Complexity: O(81) = O(1) Space Complexity: O(1) (27 integers)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
XOR tricks (this problem) O(n) O(1) Single number, swap without temp
Bit masks O(2^n) O(n) Subset enumeration
Brian Kernighan O(log n) O(1) Count set bits
Shift operations O(n) O(1) Power of two, divide by 2

Solution

class Solution:
    def isValidSudoku(self, board):
        row = [0] * 9
        col = [0] * 9
        box = [0] * 9
        
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    continue
                
                num = ord(board[i][j]) - ord('1')  # 0..8
                mask = 1 << num
                
                boxIndex = (i // 3) * 3 + (j // 3)
                
                if (row[i] & mask) or (col[j] & mask) or (box[boxIndex] & mask):
                    return False
                
                row[i] |= mask
                col[j] |= mask
                box[boxIndex] |= mask
        
        return True

Solution Explanation

Fixed size 9x9 – maximum 81 cells, so time complexity is essentially constant. This problem is not about performance; it’s about clean constraint modeling.

Common Mistakes

  • Using unordered_set inside loops – slower and messier than bitmask
  • Forgetting to skip '.' cells
  • Wrong box index formula ((i % 3) * 3 + (j % 3) is position within a box, not the box index)

Key Takeaways

This problem tests:

  • Constraint modeling – 27 groups validated in one pass
  • Bitmask usage – one integer per constraint group
  • Grid indexing mapping – the (i/3)*3 + (j/3) trick
  • Clean O(1) structure design – no containers, just arrays

References

Template Reference