Module 13 · Matrix Traversal and Simulation

130. Validate Sudoku Board

Interview · Download this solution · All solutions and shared helpers

Problem

Check a 9-by-9 Sudoku board containing characters '1' through '9' or '.' for empty cells. Return whether no filled digit repeats within any row, column or 3-by-3 box. This checks local consistency only, not whether the board can be completed.

Examples

Example 1

valid_sudoku(["123456789"] + ["........."] * 8)
=> True

One fully distinct row is locally consistent with empty remaining rows.

Example 2

valid_sudoku(["11......."] + ["........."] * 8)
=> False

A row contains two copies of one.

Example 3

valid_sudoku(["1........", ".1......."] + ["........."] * 7)
=> False

Different rows and columns can still repeat a digit inside one box.

Reveal the worked solution and reasoning

Why this mechanism works

Every filled cell belongs to three independently constrained groups. Maintain a set for each row, column and box. The box identifier is (r//3)*3+c//3, which maps the nine boxes to distinct indices.

State and boundaries

row_sets, column_sets and boxes contain digits already encountered in their respective groups.

Protocol

Skip empty cells.
Compute the cell's box index.
Reject if the digit is already in any of its three groups.
Otherwise add it to all three.
Accept after every filled cell passes.

Visualization

box index grid:
0 0 0 | 1 1 1 | 2 2 2
3 3 3 | 4 4 4 | 5 5 5
6 6 6 | 7 7 7 | 8 8 8
(each displayed band represents three rows)

Python implementation

def valid_sudoku(board):
    row_sets = [set() for _ in range(9)]
    column_sets = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            digit = board[r][c]
            if digit == '.':
                continue
            box = (r // 3) * 3 + c // 3
            if digit in row_sets[r] or digit in column_sets[c] or digit in boxes[box]:
                return False
            row_sets[r].add(digit)
            column_sets[c].add(digit)
            boxes[box].add(digit)
    return True

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

valid_sudoku(["123456789"] + ["........."] * 8)

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=0

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=1

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=2

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=3

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=4

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=5

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=6

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=7

... 147 intermediate state changes omitted ...

L6 valid_sudoku: for c in range(9):
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1', '2', '3', '4', '5', '6', '7', '8', ...}, set(), set(), set(), set(), set(), set(), se...; column_sets=[{'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'6'}, {'7'}, {'8'}, ...]; boxes=[{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '9'}, set(), set(), set(), set(), set(), ...]; r=8; c=5; digit='.'; box=2

L6 valid_sudoku: for c in range(9):
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1', '2', '3', '4', '5', '6', '7', '8', ...}, set(), set(), set(), set(), set(), set(), se...; column_sets=[{'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'6'}, {'7'}, {'8'}, ...]; boxes=[{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '9'}, set(), set(), set(), set(), set(), ...]; r=8; c=6; digit='.'; box=2

L6 valid_sudoku: for c in range(9):
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1', '2', '3', '4', '5', '6', '7', '8', ...}, set(), set(), set(), set(), set(), set(), se...; column_sets=[{'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'6'}, {'7'}, {'8'}, ...]; boxes=[{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '9'}, set(), set(), set(), set(), set(), ...]; r=8; c=7; digit='.'; box=2

L6 valid_sudoku: for c in range(9):
board=['123456789', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1', '2', '3', '4', '5', '6', '7', '8', ...}, set(), set(), set(), set(), set(), set(), se...; column_sets=[{'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'6'}, {'7'}, {'8'}, ...]; boxes=[{'1', '2', '3'}, {'4', '5', '6'}, {'7', '8', '9'}, set(), set(), set(), set(), set(), ...]; r=8; c=8; digit='.'; box=2

Result: True. One fully distinct row is locally consistent with empty remaining rows.

valid_sudoku(["11......."] + ["........."] * 8)

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=0

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=1

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=2

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=3

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=4

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=5

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=6

L2 valid_sudoku: row_sets = [set() for _ in range(9)]
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; _=7

... 26 intermediate state changes omitted ...

L13 valid_sudoku: row_sets[r].add(digit)
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; column_sets=[set(), set(), set(), set(), set(), set(), set(), set(), ...]; boxes=[set(), set(), set(), set(), set(), set(), set(), set(), ...]; r=0; c=0; digit='1'; box=0

L14 valid_sudoku: column_sets[c].add(digit)
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; column_sets=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; boxes=[set(), set(), set(), set(), set(), set(), set(), set(), ...]; r=0; c=0; digit='1'; box=0

L15 valid_sudoku: boxes[box].add(digit)
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; column_sets=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; boxes=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; r=0; c=0; digit='1'; box=0

L6 valid_sudoku: for c in range(9):
board=['11.......', '.........', '.........', '.........', '.........', '.........', '.........', ...; row_sets=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; column_sets=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; boxes=[{'1'}, set(), set(), set(), set(), set(), set(), set(), ...]; r=0; c=1; digit='1'; box=0

Result: False. A row contains two copies of one.

Why the solution is correct

A duplicate is rejected when its later occurrence is visited in the shared row, column or box. Conversely, if every membership check passes, no group contains two occurrences of any digit. The algorithm therefore checks exactly the three stated local constraints.

Time and space

O(81) time and bounded storage for a standard 9-by-9 board; the dimensions are fixed by the contract.

Common mistakes

Using r//3+c//3 merges distinct boxes. A locally valid partial board is not automatically guaranteed to have a full solution.

Reasoning card

State: row_sets, column_sets and boxes contain digits already encountered in their respective groups.

Invariant: No processed unit contains a repeated digit.

Decision to rehearse: Create three independent membership identities per filled cell.

Finish: Accept after every filled cell passes

Transfer exercise

Build a solver by maintaining these same constraints during backtracking, restoring every set when a candidate is undone.