Problem Description

You need to determine if a given 9×9 Sudoku board is valid. The board is represented as a 2D array where each cell contains either a digit from '1' to '9' or a '.' (representing an empty cell).

A valid Sudoku board must satisfy three rules:

1. Each row must contain the digits 1-9 without any repetition (considering only filled cells)
2. Each column must contain the digits 1-9 without any repetition (considering only filled cells)
3. Each of the nine 3×3 sub-boxes must contain the digits 1-9 without any repetition (considering only filled cells)

Important points to note:

• You only need to validate the filled cells according to these rules - empty cells (marked with '.') are ignored
• A board can be valid even if it's not completely filled
• A valid board doesn't need to be solvable - it just needs to follow the rules for the numbers that are already placed

For example, if a row contains ['5', '.', '.', '3', '.', '.', '.', '.', '5'], this would be invalid because the digit '5' appears twice in the same row.

The 3×3 sub-boxes are the nine non-overlapping squares that divide the 9×9 board:

• Top-left box: rows 0-2, columns 0-2
• Top-middle box: rows 0-2, columns 3-5
• Top-right box: rows 0-2, columns 6-8
• And so on for the middle and bottom rows

Your task is to return true if the board configuration is valid according to these rules, or false otherwise.

Intuition

The key insight is that we need to track which numbers have already appeared in each row, column, and 3×3 sub-box. If we encounter a number that has already been seen in its respective row, column, or sub-box, we know the board is invalid.

Think of it like having three separate "record books":

• One for tracking which numbers appear in each row
• One for tracking which numbers appear in each column
• One for tracking which numbers appear in each 3×3 sub-box

As we scan through the board cell by cell, for each filled cell we check: "Has this number already appeared in this row? In this column? In this 3×3 sub-box?" If the answer to any of these questions is "yes", we've found a violation and can immediately return false.

The tricky part is mapping each cell to its corresponding 3×3 sub-box. We can think of the nine sub-boxes as being arranged in a 3×3 grid themselves (sub-box 0-8). For a cell at position (i, j):

• The sub-box row is i // 3 (integer division)
• The sub-box column is j // 3
• The sub-box index can be calculated as (i // 3) * 3 + (j // 3)

For example, cell (5, 7) belongs to sub-box (5//3)*3 + (7//3) = 1*3 + 2 = 5.

We use boolean arrays to track whether each digit (1-9) has appeared in each row, column, and sub-box. Since we're using 0-based indexing, digit d is stored at index d-1. This gives us an efficient O(1) lookup to check if a number has been seen before.

The beauty of this approach is that we only need to traverse the board once, checking and marking as we go. If we complete the traversal without finding any conflicts, the board must be valid.

Solution Approach

We implement the solution using a single traversal approach with three 2D boolean arrays to track the appearance of digits.

Data Structures:

• row: A 9×9 boolean array where row[i][num] indicates whether digit num+1 has appeared in row i
• col: A 9×9 boolean array where col[j][num] indicates whether digit num+1 has appeared in column j
• sub: A 9×9 boolean array where sub[k][num] indicates whether digit num+1 has appeared in sub-box k

Algorithm Steps:

1. Initialize tracking arrays: Create three 9×9 boolean arrays initialized to False. Each array has 9 rows (one for each row/column/sub-box) and 9 columns (one for each possible digit 1-9).

2. Traverse the board: Use nested loops to visit each cell (i, j) in the 9×9 board.

3. Skip empty cells: If the current cell contains '.', continue to the next cell.

4. Process filled cells:

   • Convert the character digit to its numeric index: num = int(c) - 1 (subtract 1 for 0-based indexing)
   • Calculate the sub-box index: k = (i // 3) * 3 + (j // 3)
     • i // 3 gives the sub-box row (0, 1, or 2)
     • j // 3 gives the sub-box column (0, 1, or 2)
     • The formula maps to sub-boxes 0-8 in row-major order

5. Check for violations: Before marking the digit as seen, check if it already exists:

   • row[i][num]: Has this digit appeared in row i?
   • col[j][num]: Has this digit appeared in column j?
   • sub[k][num]: Has this digit appeared in sub-box k?

   If any of these is True, return False immediately.

6. Mark the digit as seen: If no violation is found, mark the digit in all three tracking arrays:

   • row[i][num] = True
   • col[j][num] = True
   • sub[k][num] = True

7. Return result: If the entire board is traversed without finding any violations, return True.

Time Complexity: O(1) - We always traverse a fixed 9×9 board, making 81 iterations.

Space Complexity: O(1) - We use three 9×9 arrays, which is a constant amount of space regardless of input.

Example Walkthrough

Let's walk through a small 4×4 simplified Sudoku example to illustrate the solution approach (using 2×2 sub-boxes instead of 3×3 for simplicity):

Board:
[1, 2, ., 4]
[3, 4, 1, .]
[., 1, 4, 3]
[4, 3, 2, 1]

Step 1: Initialize tracking arrays

• row[4][4]: all False (tracks digits 1-4 in each row)
• col[4][4]: all False (tracks digits 1-4 in each column)
• sub[4][4]: all False (tracks digits 1-4 in each 2×2 sub-box)

Step 2: Process cell (0,0) = '1'

• Digit index: 1-1 = 0
• Sub-box: (0//2)*2 + (0//2) = 0
• Check: row[0][0]? No. col[0][0]? No. sub[0][0]? No.
• Mark: row[0][0]=True, col[0][0]=True, sub[0][0]=True

Step 3: Process cell (0,1) = '2'

• Digit index: 2-1 = 1
• Sub-box: (0//2)*2 + (1//2) = 0
• Check: row[0][1]? No. col[1][1]? No. sub[0][1]? No.
• Mark: row[0][1]=True, col[1][1]=True, sub[0][1]=True

Step 4: Skip cell (0,2) = '.'

Step 5: Process cell (0,3) = '4'

• Digit index: 4-1 = 3
• Sub-box: (0//2)*2 + (3//2) = 1
• Check: row[0][3]? No. col[3][3]? No. sub[1][3]? No.
• Mark: row[0][3]=True, col[3][3]=True, sub[1][3]=True

Continue for row 1...

Step 8: Process cell (1,2) = '1'

• Digit index: 1-1 = 0
• Sub-box: (1//2)*2 + (2//2) = 1
• Check: row[1][0]? No. col[2][0]? No. sub[1][0]? No.
• Mark: row[1][0]=True, col[2][0]=True, sub[1][0]=True

Later: Process cell (2,1) = '1'

• Digit index: 1-1 = 0
• Sub-box: (2//2)*2 + (1//2) = 2
• Check:
  • row[2][0]? No (digit 1 hasn't appeared in row 2 yet)
  • col[1][0]? No (digit 1 hasn't appeared in column 1 yet)
  • sub[2][0]? No (digit 1 hasn't appeared in sub-box 2 yet)
• Mark: row[2][0]=True, col[1][0]=True, sub[2][0]=True

The board is valid! Each digit appears at most once in each row, column, and sub-box.

Invalid Example: If we had:

[1, 1, ., .]  <- Invalid: '1' appears twice in row 0

When processing cell (0,1) = '1':

• Digit index: 0
• Sub-box: 0
• Check: row[0][0]? Yes! (we already saw '1' in row 0)
• Return False immediately

This demonstrates how the algorithm efficiently detects violations by tracking seen digits in each constraint (row, column, sub-box).

Solution Implementation

Time and Space Complexity

The time complexity is O(1) and the space complexity is O(1).

Although the code contains nested loops that iterate through the 9×9 board, the board size is fixed at 81 cells. The algorithm examines each cell exactly once, performing constant-time operations (checking and updating boolean arrays) for each non-empty cell. Since the board dimensions are constant (9×9), the total number of operations is bounded by a constant value of 81.

For space complexity, the algorithm uses three 9×9 boolean arrays (row, col, and sub) to track which numbers have been used in each row, column, and 3×3 sub-box respectively. This results in 3 × 9 × 9 = 243 boolean values, which is a constant amount of space regardless of input.

The reference answer states O(C) where C = 81, which effectively equals O(81) = O(1) since 81 is a constant. The complexity doesn't grow with input size because the Sudoku board dimensions are fixed.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Sub-box Index Calculation

One of the most common mistakes is incorrectly calculating which 3×3 sub-box a cell belongs to. Developers often confuse the formula or use incorrect operations.

Incorrect approaches:

• Using box_idx = (row_idx % 3) * 3 + (col_idx % 3) - This gives the position within a box, not the box index
• Using box_idx = row_idx // 3 + col_idx // 3 - This doesn't properly enumerate the 9 boxes
• Forgetting integer division and using regular division / instead of //

Correct approach:

box_idx = (row_idx // 3) * 3 + (col_idx // 3)

This formula works because:

• row_idx // 3 gives you which row of boxes (0, 1, or 2)
• col_idx // 3 gives you which column of boxes (0, 1, or 2)
• Multiplying the row by 3 and adding the column gives boxes numbered 0-8

2. Off-by-One Errors with Digit Indexing

Since the board contains digits '1' through '9' as characters, but array indices are 0-based, forgetting to adjust the index is a frequent error.

Incorrect:

digit_idx = int(cell_value)  # Wrong! This would try to access index 9 for digit '9'

Correct:

digit_idx = int(cell_value) - 1  # Converts '1'-'9' to indices 0-8

3. Using Sets Incorrectly

While using sets is a valid alternative approach, a common mistake is creating the wrong number of sets or using string concatenation incorrectly.

Problematic approach:

seen = set()
for i in range(9):
    for j in range(9):
        if board[i][j] != '.':
            val = board[i][j]
            # These string keys must be unique and consistent
            if f"row{i}{val}" in seen:  # Easy to mess up the format
                return False
            seen.add(f"row{i}{val}")
            # ... similar for column and box

Better set-based approach:

seen = set()
for i in range(9):
    for j in range(9):
        if board[i][j] != '.':
            val = board[i][j]
            box_idx = (i // 3) * 3 + (j // 3)
            # Use tuples for clarity and type safety
            row_key = ('row', i, val)
            col_key = ('col', j, val)
            box_key = ('box', box_idx, val)
          
            if row_key in seen or col_key in seen or box_key in seen:
                return False
            seen.add(row_key)
            seen.add(col_key)
            seen.add(box_key)

4. Checking for Complete Solution Instead of Validity

Some developers mistakenly try to verify if the board is completely filled or solvable, rather than just checking if the current configuration is valid.

Wrong interpretation:

# Checking if every row has all digits 1-9
for row in board:
    if '.' in row:
        return False  # Wrong! Empty cells are allowed

Correct interpretation: The problem only asks to validate that filled cells don't violate Sudoku rules. Empty cells should be ignored, and the board doesn't need to be complete or solvable.