Solve a 9x9 Sudoku puzzle
Company: Pinterest
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given a partially filled **9×9 Sudoku** board, fill the empty cells so that the completed board is valid.
A valid Sudoku satisfies:
- Each row contains digits **1–9** with no repetition.
- Each column contains digits **1–9** with no repetition.
- Each of the nine **3×3 sub-boxes** contains digits **1–9** with no repetition.
### Input
- A 9×9 grid of characters where each cell is either `'1'..'9'` or `'.'` (empty).
### Output
- Modify the board in-place (or return the completed board) so it becomes a valid solved Sudoku.
### Assumptions / Constraints
- The input is guaranteed to have **at least one solution**.
- You may assume the puzzle has a **unique solution** unless stated otherwise.
### Example
Input:
- Row 1: `5 3 . 7 . .`
- Row 2: `6 . 1 9 5 . .`
Output: a completed valid Sudoku grid.
Overview: This question evaluates algorithmic problem-solving skills focused on constraint satisfaction, state-space search, and implementation correctness for combinatorial puzzles.
Community answers
Answer by singhalarchit1
def solve_sudoku(board):
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
box_r, box_c = 3 (row // 3), 3 (col // 3)
for i in range(box_r, box_r + 3):
for j in range(box_c, box_c + 3):
if board[i][j] == num:
return False
return True
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = '.'
return False
return True
solve(board)