Katkat
Back

Validate a 9×9 grid under constraints

VerkadaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to validate a 9x9 grid against Sudoku-like constraints using efficient lookups and index arithmetic.

Problem Statement

You are given a 9x9 grid representing a partially filled board. Your task is to determine if the grid is valid according to the following three rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3x3 sub-grids must contain the digits 1-9 without repetition.

The grid contains integers from 0 to 9, where 0 represents an empty cell. Empty cells (0) should be ignored during validation.

Implement the function is_valid_grid(grid) which returns True if the grid follows these rules, and False otherwise.

Function Signature

def is_valid_grid(grid: list[list[int]]) -> bool:
    pass

Examples

Example 1: Input: A 9x9 grid where every row, column, and sub-grid contains unique digits 1-9. Output: True

Example 2: Input: A grid where row 0 contains two '5's. Output: False

Constraints

  • The input is always a 9x9 list of lists.
  • Each cell value is an integer between 0 and 9.

Considerations

  • How will you track seen numbers efficiently for each row, column, and block?
  • Consider how to map a coordinate (r, c) to a specific 3x3 block index.

Hints

Hint 1

Use three separate sets (or boolean arrays) to track digits seen in each row, each column, and each 3x3 sub-grid.

Hint 2

A cell at `(r, c)` belongs to a 3x3 block that can be identified by the indices `(r // 3, c // 3)`.

Hint 3

Iterate through the grid once and perform lookups for all three constraints simultaneously for each non-zero cell.

Follow-up questions

  • How would your approach change if the grid size was N x N, where N is a perfect square (e.g., 16x16)?
  • Can you optimize the space complexity to use bit manipulation instead of sets?
  • If the grid was extremely large and sparse, how would you change the data representation to save memory?