DSA problem
Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: each row must contain the digits 1-9 without repetition, each column must contain the digits 1-9 without repetition, and each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note that an empty cell is represented by the character . and only the cells that are filled with a digit are checked. A board can be valid even if it is not solvable; the task is purely to confirm that no rule is currently violated by the existing digits.
A naive solution would scan each of the nine rows, then each of the nine columns, then each of the nine boxes separately, requiring three passes. A cleaner and more efficient approach validates all three constraints in a single pass over the 81 cells.
The intuition for the optimal approach is to maintain three groups of seen-digit sets: one set per row, one per column, and one per 3 x 3 box. As you visit each filled cell, compute its box index as (row / 3) * 3 + (col / 3), and check whether its digit already appears in the corresponding row set, column set, or box set. If any membership test fails the board is invalid; otherwise insert the digit into all three sets and continue. This validates the entire board in one sweep.
Examples
board = [["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"]]trueboard = [["8","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"]]falseboard = [["1","2",".",".",".",".",".",".","."],["2",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]falseConstraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or the . character
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.