DSA Valid Sudoku

The problem

Valid Sudoku checks a 9 by 9 board for repeated digits. A dot marks an empty cell. Empty cells are skipped during the check.

A unit is one row, one column, or one box of nine cells. A box is one of the nine 3 by 3 squares of the board. The board is valid when no digit repeats inside any unit.

board_one = ["53..7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_two = ["535.7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_three = ["5........", ".5.......", ".........",
               ".........", ".........", ".........",
               ".........", ".........", "........."]
empty_board = ["........." for _ in range(9)]
for name, board in [("board one", board_one), ("board two", board_two), ("board three", board_three)]:
    filled = sum(cell != "." for row in board for cell in row)
    print(name, "filled cells:", filled)
print("board one expected: True")
print("board two expected: False")
print("board three expected: False")

Board one is the clean board. Board two repeats a 5 in its first row. Board three repeats a 5 inside one box while its rows and columns stay clean.

Intuition: checking rows alone misses two thirds of the rules

A first idea checks each row for a repeat. Rows are easy to scan. The idea feels complete because every cell sits in some row.

The trap is that a repeat can hide across rows. Board three puts its two 5 digits in different rows and different columns. Only the shared box exposes them.

board_one = ["53..7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_two = ["535.7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_three = ["5........", ".5.......", ".........",
               ".........", ".........", ".........",
               ".........", ".........", "........."]
empty_board = ["........." for _ in range(9)]
def rows_only(board):
    for row in board:
        seen = set()
        for cell in row:
            if cell != ".":
                if cell in seen:
                    return False
                seen.add(cell)
    return True

print("board one, rows only:", rows_only(board_one))
print("board three, rows only:", rows_only(board_three))

The row-only check calls board three valid. The verdict is wrong. All three unit kinds need a check before the board can pass.

Brute force: check each unit kind in its own pass

The brute force makes three full passes. One pass checks the rows, one checks the columns, and one checks the boxes. Each pass rebuilds its sets from scratch.

A counter records the filled cells examined. A valid board pays the full price of all three passes.

def valid_brute(board):
    checked = 0
    for r in range(9):
        seen = set()
        for c in range(9):
            cell = board[r][c]
            if cell != ".":
                checked += 1
                if cell in seen:
                    return False, checked
                seen.add(cell)
    for c in range(9):
        seen = set()
        for r in range(9):
            cell = board[r][c]
            if cell != ".":
                checked += 1
                if cell in seen:
                    return False, checked
                seen.add(cell)
    for br in range(3):
        for bc in range(3):
            seen = set()
            for r in range(br * 3, br * 3 + 3):
                for c in range(bc * 3, bc * 3 + 3):
                    cell = board[r][c]
                    if cell != ".":
                        checked += 1
                        if cell in seen:
                            return False, checked
                        seen.add(cell)
    return True, checked

board_one = ["53..7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_two = ["535.7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_three = ["5........", ".5.......", ".........",
               ".........", ".........", ".........",
               ".........", ".........", "........."]
empty_board = ["........." for _ in range(9)]
print("board one:", valid_brute(board_one))
print("board two:", valid_brute(board_two))
print("board three:", valid_brute(board_three))

Board one pays ninety filled-cell checks for thirty filled cells. Each digit was examined three times, once per unit kind. The work is correct and tripled.

The optimal solution: one pass filling twenty-seven sets at once

Each unit keeps its own set of digits already seen. One walk over the board tests each filled cell against its row set, its column set, and its box set, then adds the digit to all three.

The box number comes from the row and the column. Integer division by three gives the box row and the box column. The pair combines into one number from 0 to 8.

def valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    checked = 0
    for r in range(9):
        for c in range(9):
            cell = board[r][c]
            if cell == ".":
                continue
            checked += 1
            box = (r // 3) * 3 + c // 3
            if cell in rows[r] or cell in cols[c] or cell in boxes[box]:
                return False, checked
            rows[r].add(cell)
            cols[c].add(cell)
            boxes[box].add(cell)
    return True, checked

board_one = ["53..7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_two = ["535.7....", "6..195...", ".98....6.",
             "8...6...3", "4..8.3..1", "7...2...6",
             ".6....28.", "...419..5", "....8..79"]
board_three = ["5........", ".5.......", ".........",
               ".........", ".........", ".........",
               ".........", ".........", "........."]
empty_board = ["........." for _ in range(9)]
print("board one:", valid_sudoku(board_one), "expected: (True, 30)")
print("board two:", valid_sudoku(board_two), "expected: (False, 3)")
print("board three:", valid_sudoku(board_three), "expected: (False, 2)")
print("empty board:", valid_sudoku(empty_board), "expected: (True, 0)")

Board one now costs thirty checks instead of ninety. Board two fails at its third filled cell. Board three fails at its second filled cell, caught by the box set.

Walkthrough: board two fails at the third filled cell

The walk visits the filled cells of the first row in order. Each step shows the digit, its box, and the row set before the digit is added.

row = "535.7...."
row_set = set()
box_set = set()
for c, cell in enumerate(row):
    if cell == ".":
        continue
    box = (0 // 3) * 3 + c // 3
    print("col", c, "digit", cell, "box", box, "- in row set:", cell in row_set, "- in box set:", cell in box_set)
    if cell in row_set or cell in box_set:
        print("repeat found, board is invalid")
        break
    row_set.add(cell)
    box_set.add(cell)

The second 5 arrives at column 2. The row set already holds a 5 from column 0. The walk stops there, and the rest of the board is never read.

Complexity

The one-pass check examines each filled cell once and does three set lookups per cell, so its time is proportional to the filled cells. The brute force examines each filled cell three times, once per pass.

The one-pass check stores twenty-seven sets, and each set holds at most nine digits, so its space stays bounded by the board size. The board itself is fixed at 81 cells.

for filled in [10, 30, 81]:
    print("filled cells", filled, "- brute checks:", filled * 3, " one-pass checks:", filled)

The saving is a constant factor, not a new growth rate. One pass still beats three passes on every board. The fixed board size keeps both designs fast in practice.

Edge cases and pitfalls

An empty board is valid. No unit holds any digit, so no repeat can exist. A valid board also need not be solvable, because this check never tries to fill the gaps.

The classic mistake is the box formula. Using the row alone names only three boxes. The column part must join the calculation, or cells from different boxes share one set and clean boards fail.

def valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            cell = board[r][c]
            if cell == ".":
                continue
            box = (r // 3) * 3 + c // 3
            if cell in rows[r] or cell in cols[c] or cell in boxes[box]:
                return False
            rows[r].add(cell)
            cols[c].add(cell)
            boxes[box].add(cell)
    return True

empty = ["........." for _ in range(9)]
one = ["5........"] + ["........." for _ in range(8)]
col_dup = ["5........", ".........", ".........", "5........"] + ["........." for _ in range(5)]
box_dup = ["5........", ".5......."] + ["........." for _ in range(7)]
far_same = ["5........"] + ["........." for _ in range(7)] + ["........5"]
print("empty board:", valid_sudoku(empty))
print("one digit:", valid_sudoku(one))
print("column repeat:", valid_sudoku(col_dup))
print("box repeat:", valid_sudoku(box_dup))
print("same digit far apart:", valid_sudoku(far_same))

The last board places its two 5 digits in different rows, different columns, and different boxes. No unit holds both digits. The board therefore passes, and rightly so.