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 only 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 ignored. The question is whether, among the filled cells, any digit repeats inside a row, a column, or a box.

The 3x3 sub-box check needs more care than the other two. Rows and columns are indexed directly by r and c, but each box covers a 3x3 block of cells, so we need a way to map a cell at (r, c) to the box that contains it.

Key Constraints

Intuition

Validate each constraint on its own. First scan every row and confirm no digit repeats, then scan every column, then scan every 3x3 sub-box. This matches how a person checks a Sudoku board by hand: read across one row looking for a repeat, move to the next row, and later repeat the process for columns and boxes.

To detect a repeat inside a single row, we walk the row and keep a set of digits seen so far. If a digit is already in the set when we reach it, the row has a duplicate and the board is invalid. The same set-based check works for columns and boxes.

Algorithm

Example Walkthrough

Take Example 2, which differs from Example 1 only in the top-left cell: board[0][0] is '8' instead of '5', and column 0 now reads 8, 6, ., 8, 4, 7, ., ., . from top to bottom.

The row pass runs first. Row 0 is 8 3 . . 7 . . . ., with filled digits 8, 3, 7, all distinct, so the set ends as {8, 3, 7} with no repeat. Rows 1 through 8 are likewise clean, so the row pass finishes without returning false.

The column pass runs next. Column 0 is processed top to bottom:

The board fails the column rule because two 8s share column 0, and the function returns false without examining the remaining columns or any box.

Code

The three-pass approach is correct, and since the board is fixed at 9x9 there is no performance penalty. The drawback is repetition: the same duplicate-checking logic is written three times, and the board is read three times. The next approach folds all three checks into a single pass.

Intuition

Check all three constraints during one walk over the board. Maintain a set for every row, every column, and every 3x3 box (27 sets in all). For each filled cell, check whether its digit already appears in its row's set, its column's set, or its box's set. If it appears in any of them, the board is invalid; otherwise add the digit to all three.

The row and column lookups are direct, but the box check needs a way to find which box a cell belongs to. The 9 boxes form a 3x3 grid of blocks. A cell's block row is r / 3 (integer division): rows 0-2 give 0, rows 3-5 give 1, rows 6-8 give 2. Its block column is c / 3 by the same logic. To store the 27 sets in flat arrays, flatten that (blockRow, blockCol) pair into a single index with the standard row-major formula blockRow * 3 + blockCol, which is (r / 3) * 3 + (c / 3). The * 3 is the number of block columns per block row, so the formula maps the nine (blockRow, blockCol) pairs to the distinct integers 0 through 8. For example, cell (5, 7) has block row 5 / 3 = 1 and block column 7 / 3 = 2, giving box index 1 * 3 + 2 = 5.

Algorithm

Example Walkthrough

Use the same Example 2 board, whose first row is 8 3 . . 7 . . . . and whose column 0 reads 8, 6, ., 8, .... Here the cells are visited in row-major order, so the failure is caught at a different point than in the three-pass version.

The duplicate 8 in column 0 is detected the moment the second 8 is read, so the function returns false at cell (3,0) without scanning the rest of the board.

Code

Maintaining 27 separate sets works but takes a few lines of setup. A common variation collapses them into one set by encoding each constraint as a distinct string key, so a single container tracks rows, columns, and boxes at once.

Intuition

Three separate sets per group exist only to keep the row, column, and box namespaces from colliding. A 5 in row 0 and a 5 in column 0 are unrelated facts, so they must not be confused. Instead of using three containers, give each fact a label that makes it unique inside one set.

When we reach a cell (r, c) with digit d, it produces three facts: digit d is in row r, in column c, and in box (r/3)*3 + (c/3). Encode each as a string such as "row 0-5", "col 0-5", and "box 0-5". Because the prefix distinguishes the three namespaces and the numbers distinguish which row, column, or box, every string is unique to one fact. Add all three to a single set; if any of the three is already present, that fact has been recorded before, which means a duplicate. The logic is identical to Approach 2, with the namespace baked into the key instead of into the choice of container.

Algorithm

Example Walkthrough

Use Example 2 once more. Cells are visited in row-major order, and each filled cell adds three keys.

The shared col 0-8 key flags the repeated 8 in column 0, and the function returns false at (3,0), matching the other approaches.

Code

This packs the bookkeeping into one container, at the cost of building and hashing a string for every fact. Approach 2 avoids the string work, and the next approach removes the hashing entirely by replacing each set with a single integer used as a bitmask, turning the membership check into one bitwise operation.

Intuition

With only nine possible digits, the set of digits seen in any row, column, or box fits in a single integer used as a bitmask. Each digit owns one bit. Setting a bit marks its digit as seen, and testing a bit checks whether the digit has appeared.

We want nine bits, one per digit, and the cheapest mapping packs them into the lowest nine bits. The character '1' should map to bit 0, '2' to bit 1, and so on through '9' to bit 8. Subtracting the character '1' from a digit character yields that 0-based offset directly: '1' - '1' = 0, '5' - '1' = 4, '9' - '1' = 8. So the mask for a digit is 1 << (digit - '1'). Subtracting '0' instead would map '1' to bit 1 and '9' to bit 9, wasting bit 0 and needing ten bits; subtracting '1' keeps the masks in bits 0 through 8.

To test whether a digit is already present, AND the group's integer with the digit's mask: a non-zero result means the bit is set and the digit is a duplicate. To record the digit, OR the mask into the integer. Both operations are single instructions, with no hashing or allocation.

Algorithm

Example Walkthrough

Use Example 2 again so the bitmask mechanics line up against the earlier traces. Integers are shown in binary with bit 0 on the right; recall '8' sets bit 7 (1 << ('8' - '1') = 1 << 7) and '6' sets bit 5.

The result matches the previous approaches: the second 8 in column 0 fails the column rule, and the function returns false at cell (3,0).

Code