Quick Overview

A coding problem that asks whether a partially filled 9x9 Sudoku board is consistent, meaning no row, column or 3x3 box repeats a digit among its filled cells. It tests careful bookkeeping of row, column and box membership without attempting to solve the puzzle.

Check Whether a Partially Filled 9x9 Sudoku Board Is Valid

Company: Confluent

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a `9 x 9` Sudoku board in which some cells are filled with digits and the rest are empty. Determine whether the filled cells are consistent with the rules of Sudoku. ### Function Signature ```python def is_valid_board(board: list[list[str]]) -> bool: ``` ### Rules - Return `True` if and only if all three conditions hold: - no row contains the same digit twice; - no column contains the same digit twice; - none of the nine `3 x 3` boxes contains the same digit twice. The boxes are the blocks formed by rows `0-2`, `3-5`, `6-8` crossed with columns `0-2`, `3-5`, `6-8`. - Only filled cells are checked. Empty cells never cause a violation. - Do not check whether the board can be completed. A board that satisfies the three conditions is valid even if no full solution extends it. ### Constraints - `len(board) == 9` and `len(board[i]) == 9` for every row `i`. - Every cell is one of the digit characters `"1"` through `"9"`, or `"."` for an empty cell. ### Examples **Example 1** ```text Input: board = [ ["2", ".", ".", "5", ".", ".", "1", ".", "."], [".", "3", ".", ".", "9", ".", ".", "6", "."], [".", ".", "7", ".", ".", "4", ".", ".", "8"], ["9", ".", ".", "6", ".", ".", "3", ".", "."], [".", "8", ".", ".", "7", ".", ".", "4", "."], [".", ".", "5", ".", ".", "1", ".", ".", "2"], ["4", ".", ".", "8", ".", ".", "7", ".", "."], [".", "1", ".", ".", "2", ".", ".", "5", "."], [".", ".", "6", ".", ".", "3", ".", ".", "9"] ] Output: True ``` No row, column or box repeats a digit among its filled cells. **Example 2** ```text Input: board = [ ["2", ".", ".", "5", ".", ".", "1", ".", "."], ["7", "3", ".", ".", "9", ".", ".", "6", "."], [".", ".", "7", ".", ".", "4", ".", ".", "8"], ["9", ".", ".", "6", ".", ".", "3", ".", "."], [".", "8", ".", ".", "7", ".", ".", "4", "."], [".", ".", "5", ".", ".", "1", ".", ".", "2"], ["4", ".", ".", "8", ".", ".", "7", ".", "."], [".", "1", ".", ".", "2", ".", ".", "5", "."], [".", ".", "6", ".", ".", "3", ".", ".", "9"] ] Output: False ``` The top-left box holds `7` at `(1, 0)` and at `(2, 2)`. No row or column repeats a digit, so the box rule alone makes the board invalid.

Overview: A coding problem that asks whether a partially filled 9x9 Sudoku board is consistent, meaning no row, column or 3x3 box repeats a digit among its filled cells. It tests careful bookkeeping of row, column and box membership without attempting to solve the puzzle.

Read the full Confluent Software Engineer interview experience this question came from

You are given a `9 x 9` Sudoku board in which some cells are filled with digits and the rest are empty. Each cell is a one-character string: a digit `"1"` through `"9"`, or `"."` for an empty cell. Rows and columns are numbered `0` through `8`. Determine whether the filled cells are consistent with the rules of Sudoku. Return `True` if and only if all three conditions hold: - no row contains the same digit twice; - no column contains the same digit twice; - none of the nine `3 x 3` boxes contains the same digit twice. The boxes are the blocks formed by rows `0-2`, `3-5`, `6-8` crossed with columns `0-2`, `3-5`, `6-8`. Only filled cells are checked. Empty cells never cause a violation. Do not check whether the board can be completed. A board that satisfies the three conditions is valid even if no full solution extends it. The board is passed as one argument: a list of 9 rows, each a list of 9 one-character strings. Return a boolean (`True`/`False` in Python, `true`/`false` in JavaScript, Java and C++). No value in this problem can exceed 2^31-1. ### Example 1 ```text Input: board = [ ["2", ".", ".", "5", ".", ".", "1", ".", "."], [".", "3", ".", ".", "9", ".", ".", "6", "."], [".", ".", "7", ".", ".", "4", ".", ".", "8"], ["9", ".", ".", "6", ".", ".", "3", ".", "."], [".", "8", ".", ".", "7", ".", ".", "4", "."], [".", ".", "5", ".", ".", "1", ".", ".", "2"], ["4", ".", ".", "8", ".", ".", "7", ".", "."], [".", "1", ".", ".", "2", ".", ".", "5", "."], [".", ".", "6", ".", ".", "3", ".", ".", "9"] ] Output: True ``` No row, column or box repeats a digit among its filled cells. ### Example 2 ```text Input: board = [ ["2", ".", ".", "5", ".", ".", "1", ".", "."], ["7", "3", ".", ".", "9", ".", ".", "6", "."], [".", ".", "7", ".", ".", "4", ".", ".", "8"], ["9", ".", ".", "6", ".", ".", "3", ".", "."], [".", "8", ".", ".", "7", ".", ".", "4", "."], [".", ".", "5", ".", ".", "1", ".", ".", "2"], ["4", ".", ".", "8", ".", ".", "7", ".", "."], [".", "1", ".", ".", "2", ".", ".", "5", "."], [".", ".", "6", ".", ".", "3", ".", ".", "9"] ] Output: False ``` The top-left box holds `7` at `(1, 0)` and at `(2, 2)`. No row or column repeats a digit, so the box rule alone makes the board invalid. ### Constraints - `len(board) == 9` and `len(board[i]) == 9` for every row `i`. - Every cell is one of the digit characters `"1"` through `"9"`, or `"."` for an empty cell. - Any number of cells, from 0 to 81, may be filled; the board need not be completable.

Constraints

  • len(board) == 9 and len(board[i]) == 9 for every row i.
  • Every cell is one of the digit characters "1" through "9", or "." for an empty cell.
  • Any number of cells, from 0 to 81, may be filled; the board need not be completable.

Examples

Input: ([['2', '.', '.', '5', '.', '.', '1', '.', '.'], ['.', '3', '.', '.', '9', '.', '.', '6', '.'], ['.', '.', '7', '.', '.', '4', '.', '.', '8'], ['9', '.', '.', '6', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '7', '.', '.', '4', '.'], ['.', '.', '5', '.', '.', '1', '.', '.', '2'], ['4', '.', '.', '8', '.', '.', '7', '.', '.'], ['.', '1', '.', '.', '2', '.', '.', '5', '.'], ['.', '.', '6', '.', '.', '3', '.', '.', '9']],)

Expected Output: True

Explanation: Source Example 1: 27 filled cells and no row, column or box repeats a digit.

Input: ([['2', '.', '.', '5', '.', '.', '1', '.', '.'], ['7', '3', '.', '.', '9', '.', '.', '6', '.'], ['.', '.', '7', '.', '.', '4', '.', '.', '8'], ['9', '.', '.', '6', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '7', '.', '.', '4', '.'], ['.', '.', '5', '.', '.', '1', '.', '.', '2'], ['4', '.', '.', '8', '.', '.', '7', '.', '.'], ['.', '1', '.', '.', '2', '.', '.', '5', '.'], ['.', '.', '6', '.', '.', '3', '.', '.', '9']],)

Expected Output: False

Explanation: Source Example 2: the top-left box holds 7 at (1, 0) and (2, 2); no row or column repeats, so the box rule alone fails.

Hints

  1. Every filled cell belongs to exactly one row, one column and one of the nine 3 x 3 boxes; the board is invalid exactly when two filled cells with the same digit share one of those groups.
  2. Empty cells ('.') never cause a violation, and you are not asked whether the board can be completed, only whether the digits already placed conflict.
  3. Two cells are in the same box exactly when their rows fall in the same band (0-2, 3-5 or 6-8) and their columns fall in the same band.

Loading coding console...

Show the approach

Approach

Scan the 81 cells once in row-major order while keeping nine 'seen' digit sets for the rows, nine for the columns and nine for the 3 x 3 boxes. Cell (r, c) belongs to box (r // 3) * 3 + c // 3, which numbers the boxes 0-8 across the row bands 0-2, 3-5, 6-8 and the column bands 0-2, 3-5, 6-8. Empty '.' cells are skipped and never recorded. For a digit, if it is already in the set of its row, its column or its box, two filled cells in one unit share that digit, so return False; otherwise record it in all three sets. If the scan finishes, return True. Invariant: before cell (r, c) is processed, each set holds exactly the digits of the already-scanned filled cells of that unit. Correctness: if some unit repeats a digit, the later of the two occurrences in scan order finds the earlier one in that unit's set, so the function returns False; conversely it returns False only when a digit genuinely repeats in a row, column or box. Edge cases: an all-empty board is valid; any number of '.' cells in one unit is fine because they are never recorded; no completion search is done, so a board with no full solution but no repeated digit is valid. The board is fixed at 9 x 9, so the work is a constant 81 cell visits and at most 3 x 81 recorded digits (O(n^2) time and space for a general n x n grid).

Time complexity:
O(1)
Space complexity:
O(1)