37/670

37. Sudoku Solver

Hard

You receive a partially filled sudoku puzzle as a list board of nine 9-character strings, where the digits 1–9 are given clues and . marks an empty cell. Complete the puzzle: fill every empty cell so that each row, each column, and each of the nine 3×3 boxes ends up containing every digit from 1 to 9 exactly once.

Return the finished board in the same nine-string format. Every input is guaranteed to admit exactly one solution, so the completed grid is fully determined by the clues.

Three constraints decide every empty cellTo fill the gold cell, gather the digits already present in its row, column, and 3×3 box (shaded gold). Whatever is missing from all three is a candidate — backtracking tries each one and undoes it if the board dead-ends later.

Example 1:

Input: board = ["..5286...", ".8.3...56", "36951....", "..87....2", "457......", "6..1.957.", ".3.....65", "5..6...29", "91..5.8.7"]

Output: ["745286913", "281394756", "369517284", "198765342", "457823691", "623149578", "832971465", "574638129", "916452837"]

Explanation: The 45 empty cells have exactly one joint assignment that satisfies all row, column, and box rules.

Example 2:

Input: board = [".5..1....", "6318.9.45", "7823.561.", "2.8534..6", ".65791.24", "4...8257.", "89.15..32", "5..92.76.", "1.746.9.8"]

Output: ["954216387", "631879245", "782345619", "278534196", "365791824", "419682573", "896157432", "543928761", "127463958"]

Explanation: With 51 clues the search barely branches: most cells are forced immediately by their row, column, and box.

Constraints:

board has exactly 9 rows and 9 columns.
board[r][c] is a digit '1'-'9' or '.'.
The given clues are consistent, and the puzzle has exactly one solution.

Hints:

Backtracking is the tool: locate an empty cell, try each digit that does not already appear in its row, column, or 3×3 box, recurse on the rest of the board, and erase the digit if the recursion dead-ends. The unique-solution guarantee means the first complete fill you reach is the answer.

Make the constraint test O(1) by keeping three arrays of 9-bit masks — one per row, column, and box — where bit d−1 means digit d is used. The candidates for a cell are the bits missing from rows[r] | cols[c] | boxes[b].

Branch on the *most constrained* empty cell (fewest candidate digits) instead of the first one you find. Forced cells (one candidate) then propagate like dominoes and the search tree collapses.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: board = ["..5286...", ".8.3...56", "36951....", "..87....2", "457......", "6..1.957.", ".3.....65", "5..6...29", "91..5.8.7"]

Expected output: ["745286913", "281394756", "369517284", "198765342", "457823691", "623149578", "832971465", "574638129", "916452837"]