We have a 9x9 Sudoku grid, and we need to check whether the current state of the board violates any of the three Sudoku rules. We are not solving the puzzle or checking if it can be solved. We just need to verify that no digit appears twice in the same row, the same column, or the same 3x3 sub-box.

The board may have empty cells (represented by '.'), and those are simply ignored. The real question is: among the filled cells, is there any duplicate where there shouldn't be one?

The key challenge is figuring out how to efficiently check all three constraints. Rows and columns are straightforward, but the 3x3 sub-box check requires a way to map each cell to its corresponding box.

Key Constraints:

Intuition

The most direct way to validate the board is to check each constraint one at a time. First, scan every row and make sure no digit repeats. Then scan every column. Then scan every 3x3 sub-box.

This mirrors exactly how a human would verify a Sudoku board: pick up a row, look for duplicates, then move to the next row. Repeat for columns and boxes.

Algorithm

Code

The three-pass approach works perfectly fine, and since the board is fixed at 9x9, there's no real performance difference. But the code is repetitive. We write nearly identical duplicate-checking logic three times. What if we could do all three checks in a single pass over the board?

Intuition

Instead of scanning the board three separate times, we can check all three constraints simultaneously. The idea is to maintain a set for every row, every column, and every 3x3 box. As we iterate through each cell once, we check whether the digit already exists in its row's set, its column's set, or its box's set.

The key insight is how to identify which box a cell belongs to. For a cell at position (r, c), integer division gives us the answer: r / 3 tells us the box's row index (0, 1, or 2), and c / 3 tells us the box's column index. So cell (5, 7) belongs to box (1, 2), which is the middle-right box. We can combine these into a single box index: (r / 3) * 3 + (c / 3), which gives a unique number from 0 to 8 for each of the nine boxes.

Algorithm

Code

The hash set approach works well, but hash sets have overhead: hashing, dynamic memory allocation, and pointer chasing. Since we're only tracking digits 1-9, we could use a fixed-size boolean array or even a single integer as a bitmask. Each digit maps to a bit position, and checking for duplicates becomes a single bitwise AND. This eliminates the hash set overhead entirely.

Intuition

Since we only have digits 1 through 9, we can represent the "seen digits" for any row, column, or box as a single integer. Each bit in the integer corresponds to a digit. Bit 1 represents digit '1', bit 2 represents digit '2', and so on up to bit 9 for digit '9'.

To check if a digit has been seen, we use a bitwise AND. To mark a digit as seen, we use a bitwise OR. This replaces hash set operations with single CPU instructions, which is as fast as it gets.

Algorithm

Code