Puzzle Checker: Validate That a Completed Puzzle Satisfies All Constraints

Question

## Problem

You are given a completed 9x9 Sudoku board. Validate that it is a correct solution: every row, column, and 3x3 box contains the digits 1-9 exactly once.

```python
def is_valid_sudoku(board: list[list[int]]) -> bool:
    # board[i][j] is an int 1-9
    pass
```

**Example:**
```
Valid board:
  [[5,3,4,6,7,8,9,1,2],
   [6,7,2,1,9,5,3,4,8],
   ...]
-> True

Invalid (duplicate 5 in row 0):
  [[5,3,4,6,7,8,9,1,5], ...]
-> False
```

## Round 2 - Variant

Extend to a general `n x n` puzzle (where n is a perfect square). Accept a board and a custom constraint function `is_valid_group(group: list[int]) -> bool` and validate using it.

```python
def is_valid_puzzle(
    board: list[list[int]],
    n: int,
    is_valid_group  # callable
) -> bool:
    pass
```

## Follow-ups

1. What is the time complexity of your validation?
2. How would you validate a partially filled board (cells may contain 0 for empty)?
3. How would you implement a Sudoku solver using backtracking with constraint propagation?
4. How would you parallelize validation of thousands of puzzle submissions?

Puzzle Checker: Validate That a Completed Puzzle Satisfies All Constraints

Question Details

Full Details

Topics

More from Karat