Valid Sudoku

Table of Contents +

Valid Sudoku looks scary because of the grid. But it is not about solving the puzzle. It is about checking the rules. The interviewer wants to see if you can track what you have already seen without scanning the same cells again and again.

🎯 The Problem

You get a 9 by 9 Sudoku board and you check if the filled cells follow the rules. You do not solve it.

What the cells mean:

  • A digit from 1 to 9 is a filled cell.
  • A dot is an empty cell.
  • A box is one of the nine small 3 by 3 squares.

The rules:

  • No row can have the same digit twice.
  • No column can have the same digit twice.
  • No 3 by 3 box can have the same digit twice.
  • Empty cells never break a rule. You only check the filled ones.
Input: a 9x9 board where row 0 is 5 3 . . 7 . . . .
Output: True


Explanation: every filled digit is unique within its row,
its column, and its 3x3 box. So the board is valid.

Empty cells never break a rule. We only check the digits that are there.

Here is how each filled cell must pass three checks before we trust it.

a cell has digit d

seen d in this row?

seen d in this column?

seen d in this box?

if any is yes -> invalid

else mark d as seen -> keep going

🐢 Approach 1: Separate Rescans (Brute Force)

The idea in one line: check each rule with its own scan of the board.

The idea:

  • Scan once for rows. Look for a repeated digit in each row.
  • Scan again for columns. Same check per column.
  • Scan again for boxes. Same check per box.

How it works:

  • Each scan compares every digit against the others in its group.
  • That is nested checking inside every group.

Why it is weak:

  • You pass over the same cells many times.
  • The nested comparing makes the code long and repeats work.
  • All three checks can be done in a single walk instead.

Here is the separate-rescan code:

valid_sudoku_rescans.py
def is_valid_sudoku(board):
    def valid(values):
        nums = [value for value in values if value != "."]
        return len(nums) == len(set(nums))


    for row in board:
        if not valid(row):
            return False
    for col in range(9):
        if not valid([board[row][col] for row in range(9)]):
            return False
    for box_row in range(0, 9, 3):
        for box_col in range(0, 9, 3):
            box = [board[r][c] for r in range(box_row, box_row + 3) for c in range(box_col, box_col + 3)]
            if not valid(box):
                return False
    return True

⚡ Approach 2: One Pass With Hash Sets (Best)

The idea in one line: walk the board once and check all three rules at each cell.

The idea:

  • A hash set stores items and tells you instantly if an item is already inside.
  • Keep nine sets for rows, nine for columns, nine for boxes.
  • Each set remembers the digits its group has already seen.

How it works:

  • Reach a cell with a digit.
  • Ask three questions. Is the digit in its row set, its column set, or its box set?
  • If any answer is yes, a rule is broken, so return false.
  • If all three are no, add the digit to those three sets and move on.

The box trick:

  • Find the box with (row / 3) * 3 + (col / 3).
  • That turns a cell’s position into a box number from 0 to 8.

Why it is fast:

  • Each cell is visited once.
  • Set lookups are instant, so the whole board is checked in one pass.

Here is a dry run on the first few cells of row 0.

cell 0,0 = 5

row0 has 5? no -> add

cell 0,1 = 3

row0 has 3? no -> add

cell 0,4 = 7

row0 has 7? no -> add -> still valid

Steps to Solve

  1. Make nine sets for rows, nine for columns, and nine for boxes.
  2. Walk every cell of the board with its row and column index.
  3. If the cell is empty, skip it.
  4. Find the box number with (row / 3) * 3 + (col / 3).
  5. If the digit is already in the row set, column set, or box set, return false.
  6. Otherwise add the digit to all three sets and continue. If you finish, return true.

This Python version uses sets for each row, column, and box.

valid_sudoku.py
def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]    # rows[r] holds digits seen in row r
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]


    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue                # skip empty cells
            b = (r // 3) * 3 + (c // 3)  # which 3x3 box
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False            # duplicate found
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True




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'],
]
print(is_valid_sudoku(board))

The output of the above code will be:

True

Let us walk through the Python version line by line, so the box math makes sense.

The lines rows = [set() for _ in range(9)] and the two after build nine empty sets for each group. Set number r will remember every digit seen in row r.

The two loops for r in range(9): and for c in range(9): visit every cell. The variable ch holds the character in that cell.

The check if ch == '.': skips empty cells. An empty cell never breaks a rule, so we move on.

The line b = (r // 3) * 3 + (c // 3) finds the box number. The // is integer division, so it drops the remainder. So r // 3 tells which band of rows we are in, 0, 1, or 2. Same for the columns. Putting them together gives a box number from 0 to 8.

The check if ch in rows[r] or ch in cols[c] or ch in boxes[b]: asks the three rules at once. If the digit is already in any of those sets, the board is invalid, so we return False.

If all three are clear, the three add lines record the digit in its row, column, and box. So later cells will see it. If we finish the whole board with no clash, we return True.

⏱️ Time and Space Complexity

The board is always 9 by 9, so it has a fixed number of cells. The optimal solution touches each cell once and does instant set checks. So it runs in constant time for this fixed board, which we write as O(1). The brute force rescans the cells several times, so it does more work for the same result.

Approach Time Complexity Space Complexity
Brute force (separate rescans) O(1) but several passes O(1)
One pass with hash sets O(1) O(1)

Tip

The trick interviewers love here is the box index formula. Say it out loud: (row / 3) * 3 + (col / 3). It turns a cell’s position into one of nine box numbers. Get that right and the rest is easy.

🧩 Key Takeaways

  • ✅ You only check the rules. You do not solve the puzzle.
  • ✅ Keep a hash set for each row, each column, and each box.
  • ✅ The box number is (row / 3) * 3 + (col / 3).
  • ✅ One pass over the board does all three checks at the same time.
  • ✅ Skip empty cells, because they can never break a rule.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does the Valid Sudoku problem ask you to do?

    Why: You only validate the current board against the rules. You do not solve it.

  2. 2

    Which formula finds the 3x3 box number for a cell at row r and column c?

    Why: (r / 3) * 3 + (c / 3) maps the cell into one of the nine boxes, numbered 0 to 8.

  3. 3

    Why do we keep three separate sets per group in the optimal solution?

    Why: Each group needs its own memory of seen digits so all three rules can be checked in a single pass.

  4. 4

    What happens when the current cell is empty (a dot)?

    Why: Empty cells never violate a rule, so we simply skip them and move to the next cell.

Score: 0 / 4

🚀 What’s Next?

Previous Top K Frequent Elements Next Subdomain Visit Count