Question

1. valid sudoku

determine if a (9 \times 9) sudoku board is valid. only the filled cells need to be validated according to the following rules:

1. each row must contain the digits (1-9) without repetition.
2. each column must contain the digits (1-9) without repetition.
3. each of the nine (3 \times 3) sub-boxes of the grid must contain the digits (1-9) without repetition.

note:

• a sudoku board (partially filled) could be valid but is not necessarily solvable.
• only the filled cells need to be validated according to the mentioned rules.

Explanation:

🆕 New Concept Discovered: Hash Set Lookup
Using unique keys to track duplicates in groups.

Step 1: Understand the constraints

To determine if a \(9 \times 9\) Sudoku board is valid, we must verify three conditions for the filled cells (non-empty cells containing digits '1' through '9'):

1. No duplicate digits in any row.
2. No duplicate digits in any column.
3. No duplicate digits in any of the nine \(3 \times 3\) sub-boxes.

We do not need to solve the Sudoku; we only need to check if the current state violates any of these three rules.

Step 2: Design a tracking mechanism

To check for duplicates efficiently, we can use hash sets. A hash set allows us to store elements and check if an element has been seen before in \(O(1)\) time.

We can represent the presence of a digit in three ways:

• Rows: Track seen digits using a unique identifier for each row, such as "row " + r + " has " + val.
• Columns: Track seen digits using a unique identifier for each column, such as "col " + c + " has " + val.
• Sub-boxes: The board has nine \(3 \times 3\) sub-boxes. We can map any cell coordinate \((r, c)\) to a sub-box index using integer division:

$$ \text{box\_row} = \lfloor r / 3 floor, \quad \text{box\_col} = \lfloor c / 3 floor $$

This gives us a unique coordinate pair \((\text{box\_row}, \text{box\_col})\) for each of the nine boxes. We can represent this as "box " + (r/3) + "-" + (c/3) + " has " + val.

Step 3: Algorithm implementation

We iterate through every cell \((r, c)\) on the \(9 \times 9\) board:

1. If the cell is empty (usually represented by '.'), we skip it.
2. If the cell contains a digit val, we generate its three corresponding string keys:

• row_key = f"row {r} {val}"
• col_key = f"col {c} {val}"
• box_key = f"box {r//3}-{c//3} {val}"

1. We check if any of these keys already exist in our global hash set:

• If any key is already present, it means we have found a duplicate in that row, column, or box. We immediately return False.
• If none of the keys are present, we add all three keys to our set and continue.

1. If we finish checking the entire board without finding any duplicates, we return True.

Python Code Example

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        seen = set()
        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val != '.':
                    row_key = f"row {r} {val}"
                    col_key = f"col {c} {val}"
                    box_key = f"box {r//3}-{c//3} {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)
        return True

Answer:

To determine if a \(9 \times 9\) Sudoku board is valid, iterate through each cell and use a hash set to track seen numbers across rows, columns, and \(3 \times 3\) sub-boxes.

For any filled cell at row \(r\) and column \(c\) containing digit \(v\):

• Check if \(v\) already exists in row \(r\).
• Check if \(v\) already exists in column \(c\).
• Check if \(v\) already exists in the sub-box indexed by \((\lfloor r/3

floor, \lfloor c/3
floor)\).

If any duplicate is detected, the board is invalid (False). If the entire board is scanned without duplicates, the board is valid (True).