Valid Sudoku

Determine if a 9 x 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 x 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.

For example, is this board valid?

board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

## Valid Sudoku

### Problem Description

Determine if a 9 x 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 x 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.

### Naive Solution

The most straightforward approach is to iterate through each row, column, and 3x3 sub-box and check for duplicates. We can use sets to keep track of the numbers encountered so far in each row, column, and sub-box. If we encounter a duplicate, the board is invalid. Otherwise, if we reach the end without finding any duplicates, the board is valid.

```python
def isValidSudoku_naive(board):
    n = 9

    # Check rows
    for i in range(n):
        row_set = set()
        for j in range(n):
            if board[i][j] != '.':
                if board[i][j] in row_set:
                    return False
                row_set.add(board[i][j])

    # Check columns
    for j in range(n):
        col_set = set()
        for i in range(n):
            if board[i][j] != '.':
                if board[i][j] in col_set:
                    return False
                col_set.add(board[i][j])

    # Check 3x3 sub-boxes
    for box_row in range(3):
        for box_col in range(3):
            box_set = set()
            for i in range(box_row * 3, box_row * 3 + 3):
                for j in range(box_col * 3, box_col * 3 + 3):
                    if board[i][j] != '.':
                        if board[i][j] in box_set:
                            return False
                        box_set.add(board[i][j])

    return True

Optimal Solution

The optimal solution still involves checking rows, columns, and 3x3 sub-boxes for duplicates. However, we can combine the checks into a single loop to improve efficiency. This involves using a single iteration to check all three conditions at once.

def isValidSudoku(board):
    n = 9
    rows = [set() for _ in range(n)]
    cols = [set() for _ in range(n)]
    boxes = [set() for _ in range(n)]

    for i in range(n):
        for j in range(n):
            num = board[i][j]
            if num != '.':
                num = int(num)
                box_index = (i // 3) * 3 + j // 3

                if (num in rows[i] or
                    num in cols[j] or
                    num in boxes[box_index]):
                    return False

                rows[i].add(num)
                cols[j].add(num)
                boxes[box_index].add(num)

    return True

Big(O) Run-Time Analysis

The run-time complexity of the optimal solution is O(N^2), where N is the size of the Sudoku board (9 in this case). This is because we iterate through each cell of the board once. Although there are multiple checks within the loops, the number of operations is still proportional to the number of cells in the board.

Big(O) Space Usage Analysis

The space complexity of the optimal solution is O(N), where N is the size of the Sudoku board. This is because we use three sets (rows, cols, and boxes) to store the numbers encountered so far in each row, column, and 3x3 sub-box. In the worst case, each set can contain up to 9 elements.

Edge Cases and Handling

1. Empty Board: An empty board (all cells are '.') is considered valid as there are no conflicting numbers. Our solution correctly handles this case by skipping empty cells.
2. Invalid Characters: The board might contain characters other than digits 1-9 and '.'. Our solution only considers digits and skips '.'. If we need to explicitly validate the characters, we can add a check at the beginning of the loop.
3. Partially Filled Board: The board might be partially filled with some valid and some invalid placements. Our solution correctly identifies whether the filled cells are valid according to Sudoku rules.
4. Large Input: Although Sudoku boards are typically 9x9, a more general solution can be made to handle boards of different sizes.