Valid Sudoku

Validation does not require solving the Sudoku. Scan every nonempty cell and ensure its digit has not already appeared in its row, column, or 3-by-3 box. Keep three collections of sets, or encode keys such as row:r:digit, col:c:digit, and box:b:digit in one set. The box index is (r/3)*3 + c/3 using integer division. If any lookup finds a duplicate, return false immediately; otherwise add all three keys and finish true. For the fixed 9-by-9 board this is constant bounded work, conventionally O(81) time and O(81) space, or O(n^2) for generalized n-by-n boards. Test empty cells, duplicate in a box but not direct row/column, and invalid characters if input is not guaranteed clean. Explain that no backtracking is needed.