Valid Sudoku

mediumPROMath & GeometryUber DSA

Determine if a 9x9 Sudoku board is valid. Only filled cells need to be validated: each row, column, and 3x3 box must contain digits 1-9 without repetition.

Input: 9 rows, each with 9 comma-separated values ('.' for empty).

Example

Input

5,3,.,.,7,.,.,.,.
6,.,.,1,9,5,.,.,.
.,9,8,.,.,.,.,6,.
8,.,.,.,6,.,.,.,3
4,.,.,8,.,3,.,.,1
7,.,.,.,2,.,.,.,6
.,6,.,.,.,.,2,8,.
.,.,.,4,1,9,.,.,5
.,.,.,.,8,.,.,7,9

Output

True

Reasoning

The input is a 9x9 Sudoku board represented as 9 rows of comma-separated values, where '.' denotes an empty cell.
We iterate over each row, column, and 3x3 box to check for duplicate digits (1-9), ignoring empty cells ('.').
For each row, column, and box, we verify that all filled cells contain unique digits, i.e., no digit appears more than once: $count(digits) = count(unique\_digits)$ .
Since no duplicates are found in any row, column, or box, the Sudoku board is valid, resulting in an output of True.

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'

More from Uber DSA

Two Sumeasy Group Anagramsmedium Min Stackmedium LRU Cachemedium Missing Numbereasy

Concept primerPREVIEW

Background Knowledge

The Sudoku problem is a classic example of a constraint satisfaction problem, which is a fundamental concept in computer science and mathematics. In this problem, we have a 9x9 grid, divided into nine 3x3 sub-grids or boxes. The goal is to determine if the given Sudoku board is valid, meaning each row, column, and 3x3 box contains the digits 1-9 without repetition. To solve this problem, we need to understand the concept of sets and hashing, as we will be using these data structures to keep track of the unique elements in each row, column, and box.

The problem can be broken down into three main parts: checking the validity of each row, column, and 3x3 box. We need to ensure that each of these regions contains the digits 1-9 without repetition. This can be achieved by using a set data structure, which automatically eliminates duplicates. We can also use hashing to keep track of the elements we have seen so far in each region.

In terms of mathematical concepts, this problem involves basic set theory and combinatorics. We need to understand how to iterate over the elements of a set and check for duplicates. We also need to understand how to divide the 9x9 grid into 3x3 sub-grids and iterate over these regions.

Algorithm/Approach

The general approach to solve this type of problem is to use a brute force algorithm, which involves checking each region (row, column, and 3x3 box) individually. We can use a set data structure to keep track of the unique elements in each region. We will iterate over each element in the Sudoku board, and for each element, we will check if it is already present in the corresponding set. If it is, we return False, indicating that the Sudoku board is not valid. If we finish checking all elements without finding any duplicates, we return True, indicating that the Sudoku board is valid.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results