Verify Sudoku Board

Validate a NumPlace puzzle board to ensure it follows the core rules: each row, column, and block contains unique digits. This tests your ability to use data structures for efficient constraint validation, a common pattern in problem-solving.

arrayhash-setvalidationmatrixconstraints

Problem Statement

You are given a partially filled NumPlace puzzle board represented as a 2D array (list of lists) of integers. The board is N x N, where N is a perfect square (e.g., 4x4, 9x9, 16x16). Some cells are filled with digits from 1 to N, while empty cells are represented by 0. Determine whether the current state of the board is valid according to the following rules: Each row must contain the digits 1 to N without repetition. Each column must contain the digits 1 to N without repetition. Each sqrt(N) x sqrt(N) subgrid (block) must contain the digits 1 to N without repetition. A board is considered invalid if ANY of these rules are broken. You do NOT need to solve the puzzle, only validate its current state.

Example 1

Input: [[1, 4, 2, 3], [2, 3, 1, 4], [4, 1, 3, 2], [3, 2, 4, 1]]

Output: True

This is a valid 4x4 NumPlace board as each row, column, and 2x2 block contains unique numbers from 1 to 4.

Example 2

Input: [[1, 2, 3, 4], [3, 4, 1, 2], [2, 1, 4, 3], [4, 3, 2, 2]]

Output: False

This is an invalid 4x4 NumPlace board. In the last row, the number 2 is repeated, violating the row constraint.

Constraints

-The board will always be a square (N x N).
-N will always be a perfect square (e.g., 4, 9, 16).
-Each cell will contain a number between 0 and N, inclusive.
-0 represents an empty cell.
-The board size will be at least 4x4.

Brute Force Approach

Imagine manually checking a completed puzzle. The brute-force approach is like taking each number on the board and comparing it to every other number in its row, column, and block. If you find a duplicate, the board is invalid. This involves nested loops to check each cell against all other relevant cells.

TimeO(N^3)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem