Complete a 9x9 Sudoku Puzzle That Has Exactly One Solution

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

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

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.

Complete the Unique Sudoku Solution

You are given a 9 x 9 Sudoku puzzle board 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.

Each cell is a one-character string: a digit '1' through '9', or '.' for an empty cell. No numeric value crosses the function boundary, so nothing can exceed 2^31 - 1.

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.

Example 1

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.

Example 2

Input: the Example 1 output with only the bottom-right cell board[8][8] replaced by '.'.

Output: the Example 1 output. Row 8 already holds '1' through '8', so the only digit that completes it is '9'.

Hints

1. Only the '.' cells may change: every given digit must appear unchanged in the returned board.
2. A digit may be placed in an empty cell only if it does not already appear in that cell's row, column, or 3 x 3 box; the box containing cell (r, c) starts at row 3 * (r // 3) and column 3 * (c // 3).
3. The completion is guaranteed to be unique, so no tie-breaking is needed: any fully filled board that keeps the givens and obeys every row, column and box rule is the expected answer.

Approach

Algorithm: copy the board, then keep three arrays of 9-bit masks recording which digits are already used in each row, each column and each box, where cell (r, c) belongs to box (r // 3) * 3 + c // 3. Collect the empty cells. Recursive search: among the cells that are still empty, choose one with the fewest allowed digits (a digit is allowed when its bit is absent from the cell's row, column and box masks). If some empty cell has no allowed digit, this branch is a dead end and returns false; if no empty cell remains, the board is complete and the search returns true. Otherwise try each allowed digit of the chosen cell in increasing order: write it, set its bit in the three masks and recurse; if the recursion fails, clear the bits and restore '.'.

Invariant: the masks always describe exactly the digits currently on the board, so a newly written digit never repeats inside its row, column or box.

Correctness: the search discards only partial boards that already repeat a digit in some row, column or box, so it explores every valid completion of the givens. When it reaches a full board, each of the 27 rows, columns and boxes holds nine distinct digits from 1 to 9, which is each digit exactly once. Givens are never modified because only cells that were empty are ever written. The source guarantees exactly one valid completion, so the first full board found is the answer and no tie-break is needed. Choosing the most constrained cell first fills forced cells immediately and keeps the branching small on hard puzzles where no cell is forced.

Edge cases: a single empty cell (including the last cell (8, 8) and the digit '9'), an entirely empty row, column or box, every copy of one digit missing, cells on box boundaries where only the box rule separates two candidates, and minimal 17-given puzzles that need deep search.

• Time complexity: O(m * 9^m) in the worst case for m empty cells (m <= 81), which is a constant bound for the fixed 9 x 9 board
• Space complexity: O(m) for the recursion stack and the list of empty cells, plus O(1) for the 27 bitmasks and the 9 x 9 copy