Determine if a 9×9 Sudoku board is valid. Only filled cells need to be validated: each row, each column, and each of the nine 3×3 boxes must contain the digits 1–9 without repetition. Empty cells are marked '.'.
board = (classic valid Sudoku board)trueboard = (board with '8' duplicated in column 0)false'1'–'9' or '.'seenseen set)'.'. Compute box = (r/3)*3 + c/3row[r], col[c], or box[box] → return falsetrueThe board is always exactly 9×9 with at most 81 cells, so both time and space are O(1) — bounded by a constant. Three families of sets (rows, columns, boxes) guarantee that each constraint unit is checked independently. The single-pass scan never backtracks: the moment a duplicate is found in any unit, we immediately return false.
You could check every row, then every column, then every box, in three separate passes. One pass with sets for all three is cleaner.
Keep 9 sets for the rows, 9 for the columns, and 9 for the boxes. The box index of a cell is row divided by 3, times 3, plus column divided by 3. For each filled cell, if its digit is already in its row, column or box set, the board is invalid. Otherwise add the digit to all three sets.
One pass, 27 sets, three checks per cell. Box index equals row over 3, times 3, plus column over 3.
Run the animation above on your own input, or watch the 1:42 video explanation of Valid Sudoku with a dry run and Java code.