Validate and Complete a Partially Filled 9x9 Sudoku Board

A 9 × 9 Sudoku board is partially filled with digits. Check whether the given digits are consistent with the rules of Sudoku and, if the board can be completed, return a completed board.

Function Signature

def complete_sudoku(board: list[str]) -> list[str]:

board[r][c] is the cell in row r and column c, both 0-indexed: a digit '1' to '9', or '.' for an empty cell.

Rules

• A completed board is valid when every row, every column and each of the nine 3 × 3 boxes contains each digit from 1 to 9 exactly once. The boxes are formed by grouping rows 0–2, 3–5 and 6–8 with columns 0–2, 3–5 and 6–8.
• A completion keeps every given digit unchanged and fills every empty cell with a digit.
• If the given digits already break the rules, meaning that some digit appears twice in one row, one column or one box, return [].
• If the given digits do not break the rules but no valid completion exists, return [].
• Otherwise return a valid completion as a list of 9 strings of 9 digits each. If more than one valid completion exists, return the one whose 81 digits, read row by row from top to bottom and left to right within each row, form the smallest string. Equivalently, at the first cell where two completions differ, prefer the one with the smaller digit.
• A board with no empty cells is returned unchanged if it is valid, and [] otherwise.

Constraints

• len(board) == 9, and len(board[r]) == 9 for every row r.
• Every character is one of '1' to '9' or '.'.
• Any number of cells, from 0 to 81, may be empty.

Examples

Example 1

Input:
 board = ["1.3456789",
 "456.89123",
 "789123456",
 "2345.7891",
 "56789.2.4",
 "89123456.",
 "3456789.2",
 "678912345",
 ".12345678"]
Output:
 ["123456789",
 "456789123",
 "789123456",
 "234567891",
 "567891234",
 "891234567",
 "345678912",
 "678912345",
 "912345678"]

Rows 0, 1, 3, 5, 6 and 8 each miss exactly one digit, which fixes their empty cell. Row 4 misses 1 and 3, in columns 5 and 7; column 5 already holds a 3 in row 2, so row 4 gets 1 in column 5 and 3 in column 7. The completion is unique.

Example 2

Input:
 board = ["3........",
 ".3.......",
 ".........",
 ".........",
 ".........",
 ".........",
 ".........",
 ".........",
 "........."]
Output:
 []

The two 3s are in different rows and different columns, but both lie in the top-left box.

Example 3

Input:
 board = ["12345678.",
 ".........",
 ".........",
 ".........",
 "........9",
 ".........",
 ".........",
 ".........",
 "........."]
Output:
 []

No digit repeats in any row, column or box. However, the only digit missing from row 0 is 9, and column 8 already contains a 9 in row 4, so the cell in row 0, column 8 cannot be filled.