Complete a 9x9 Sudoku Puzzle That Has Exactly One Solution
Company: Confluent
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a `9 x 9` Sudoku puzzle in which some cells are filled with digits and the rest are empty. Fill every empty cell so that the completed board is a valid Sudoku solution, and return the completed board.
### Function Signature
```python
def solve_sudoku(board: list[list[str]]) -> list[list[str]]:
```
### Rules
- In the completed board, every row, every column and every one of the nine `3 x 3` boxes contains each digit `"1"` through `"9"` exactly once. The boxes are the blocks formed by rows `0-2`, `3-5`, `6-8` crossed with columns `0-2`, `3-5`, `6-8`.
- Every filled cell of the input keeps its digit.
- The input has exactly one valid completion, so the returned board is unique.
- Return the completed board as a `9 x 9` list of single-digit strings. You may fill the input board in place and return it.
### Constraints
- `len(board) == 9` and `len(board[i]) == 9` for every row `i`.
- Every input cell is one of `"1"` through `"9"`, or `"."` for an empty cell.
- The puzzle is guaranteed to have exactly one solution.
### Examples
**Example 1**
```text
Input: board = [
["2", "6", "4", "5", ".", "8", "1", "9", "7"],
[".", "3", "8", "1", "9", "7", "2", "6", "4"],
["1", "9", "7", "2", "6", "4", "5", ".", "8"],
["9", ".", "2", ".", ".", ".", "3", "8", "1"],
["3", "8", "1", ".", ".", ".", ".", "4", "5"],
["6", "4", "5", ".", ".", ".", "9", "7", "."],
["4", "5", ".", "8", "1", "9", "7", "2", "6"],
["8", "1", "9", "7", "2", ".", "4", "5", "3"],
["7", "2", "6", ".", "5", "3", "8", "1", "9"]
]
Output: [
["2", "6", "4", "5", "3", "8", "1", "9", "7"],
["5", "3", "8", "1", "9", "7", "2", "6", "4"],
["1", "9", "7", "2", "6", "4", "5", "3", "8"],
["9", "7", "2", "6", "4", "5", "3", "8", "1"],
["3", "8", "1", "9", "7", "2", "6", "4", "5"],
["6", "4", "5", "3", "8", "1", "9", "7", "2"],
["4", "5", "3", "8", "1", "9", "7", "2", "6"],
["8", "1", "9", "7", "2", "6", "4", "5", "3"],
["7", "2", "6", "4", "5", "3", "8", "1", "9"]
]
```
All 63 given digits are kept, and each row, column and box of the output contains `1` through `9` exactly once.
Overview: A coding problem that asks you to complete a 9x9 Sudoku puzzle that has exactly one solution, keeping every given digit and filling each row, column and 3x3 box with the digits 1 to 9. It tests constraint tracking and systematic search over the empty cells.
Read the full Confluent Software Engineer interview experience this question came from