Introduction

Checking whether a Sudoku board is valid is a classic constraint-validation problem. You need to ensure rows, columns, and three-by-three boxes contain no duplicate digits. A clean algorithm can validate a board in one pass with constant extra space relative to board size.

Sudoku Validation Rules

For a standard nine-by-nine board:

• each row can contain digits one to nine at most once
• each column can contain digits one to nine at most once
• each three-by-three box can contain digits one to nine at most once

Empty cells are allowed in partial puzzles and should be ignored during duplicate checks.

Data Representation Choices

Common board encodings:

• strings with dot for empty cells
• integers with zero for empty cells
• characters with digit symbols

The validation strategy is same regardless of representation, as long as you normalize values consistently.

One-Pass Set-Based Validator

A practical and readable approach uses three arrays of sets:

• one set per row
• one set per column
• one set per box

1from typing import List
2
3Board = List[List[str]]
4
5
6def is_valid_sudoku(board: Board) -> bool:
7    rows = [set() for _ in range(9)]
8    cols = [set() for _ in range(9)]
9    boxes = [set() for _ in range(9)]
10
11    for r in range(9):
12        for c in range(9):
13            value = board[r][c]
14            if value == ".":
15                continue
16
17            if value < "1" or value > "9":
18                return False
19
20            box = (r // 3) * 3 + (c // 3)
21
22            if value in rows[r] or value in cols[c] or value in boxes[box]:
23                return False
24
25            rows[r].add(value)
26            cols[c].add(value)
27            boxes[box].add(value)
28
29    return True
30
31
32sample = [
33    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
34    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
35    [".", "9", "8", ".", ".", ".", ".", "6", "."],
36    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
37    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
38    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
39    [".", "6", ".", ".", ".", ".", "2", "8", "."],
40    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
41    [".", ".", ".", ".", "8", ".", ".", "7", "9"],
42]
43
44print(is_valid_sudoku(sample))

This solution is easy to reason about and fits most interview and production validation needs.

Bitmask Variant for Compactness

A faster and memory-compact variant tracks seen digits with bitmasks.

1from typing import List
2
3
4def is_valid_sudoku_bitmask(board: List[List[str]]) -> bool:
5    row_mask = [0] * 9
6    col_mask = [0] * 9
7    box_mask = [0] * 9
8
9    for r in range(9):
10        for c in range(9):
11            ch = board[r][c]
12            if ch == ".":
13                continue
14            if ch < "1" or ch > "9":
15                return False
16
17            bit = 1 << (ord(ch) - ord("1"))
18            box = (r // 3) * 3 + (c // 3)
19
20            if row_mask[r] & bit or col_mask[c] & bit or box_mask[box] & bit:
21                return False
22
23            row_mask[r] |= bit
24            col_mask[c] |= bit
25            box_mask[box] |= bit
26
27    return True

Bitmasks are useful in performance-sensitive solvers and backtracking engines.

Complexity Analysis

For a fixed nine-by-nine board, runtime is effectively constant in practical terms. In generalized form for board size n by n, this validator runs in O of n squared time with O of n auxiliary structures.

The key win is single-pass validation with immediate failure on first conflict.

Integrating with Sudoku Solvers

Validation is usually a guard step before running a full solver. If input puzzle is invalid, you should fail early and avoid expensive search.

Typical flow:

1. parse input board
2. validate structure and constraints
3. run solver only when valid
4. verify solved output consistency

This separation simplifies debugging and improves solver reliability.

Testing Strategy

Useful tests include:

• valid partial board
• duplicate in one row
• duplicate in one column
• duplicate in one box
• invalid character input

You can also generate random valid complete boards and remove cells to stress-test parser and validator combinations.

Common Pitfalls

A common pitfall is calculating wrong box index and mixing cells between neighboring boxes. Another is treating empty markers as regular values and triggering false duplicates. Teams also often skip input normalization and allow unexpected symbols, causing inconsistent behavior later in solver code. Finally, validating only rows and columns while forgetting box constraints results in boards incorrectly marked valid.

Summary

• Sudoku validation checks rows, columns, and boxes for duplicates.
• A one-pass set-based solution is clear and robust.
• Bitmask approach offers compact high-performance validation.
• Validate puzzle before solving to fail fast on bad input.
• Cover row, column, box, and input-format edge cases in tests.