Katkat
Back

Check Whether a Partially Filled 9x9 Sudoku Board Is Valid

ConfluentSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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

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

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

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.