Sudoku Solver | DrawCode

1. One-Liner

Sudoku Solver picks an empty cell, tries digits 1–9 that respect Sudoku rules, and undoes on failure until the grid is complete.

2. The Problem It Solves

Given a partially filled 9×9 grid, fill remaining cells with 1..9 so each row, column, and 3×3 box contains no duplicate. Multiple solutions may exist; typical tasks require one valid completion or reporting unsolvable input.

3. The Core Idea

Choose → constrain → recurse → backtrack: assign a legal digit to an empty cell; if that leads to a dead end later, erase and try the next digit. Empty-cell order (e.g. most constrained first) prunes the tree faster but the same backtracking skeleton applies.

4. How It Works (Step-by-Step)

Step	What Happens
1. Find empty	Scan for cell with `0` or `'.'`
2. Try digit	For `1..9`, check row, column, 3×3 box
3. Place	Write digit and recurse
4. Success	If no empty left, solved
5. Fail	Clear cell, try next digit
6. Unsolvable	All digits fail at some branch

5. Dry Run Example

A cell has only {4,7} possible; try 4 → later contradiction → backtrack, try 7 → completes. Shows propagation of constraints through recursion.

6. Key Properties

Property	Value
CSP structure	Variables = cells, domains = digits
Inference	Optional: forward checking, arc consistency
Typical interview	Plain backtracking + validity check

7. Where It Is Used

Domain	Use
Puzzle apps	Hint engines and full solvers
Scheduling	Analogous “fill under constraints” problems
Education	Backtracking on 2D grids

8. Interview Tips

Clarify input format, implement clean valid(board,r,c,num), pick next empty in fixed order first, then mention MRV (minimum remaining values) as optimization.

9. Comparison with Other Approaches

Approach	Idea	Notes
Backtracking	DFS over assignments	Standard baseline
DLX / dancing links	Exact cover	Faster for hard puzzles
CP-SAT solvers	General CSP	Overkill for interviews

10. Complexity

Metric	Value
Time	Worst-case enormous; constraints prune heavily
Space	O(1) grid for fixed `9×9` (recursion stack bounded)

Implementation Example (PYTHON)

def solve_sudoku(board: list[list[int]]) -> bool:
    def find_empty():
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    return i, j
        return None
    def valid(r: int, c: int, num: int) -> bool:
        for x in range(9):
            if board[r][x] == num or board[x][c] == num:
                return False
        br, bc = 3 * (r // 3), 3 * (c // 3)
        for i in range(br, br + 3):
            for j in range(bc, bc + 3):
                if board[i][j] == num:
                    return False
        return True
    cell = find_empty()
    if not cell:
        return True
    r, c = cell
    for n in range(1, 10):
        if valid(r, c, n):
            board[r][c] = n
            if solve_sudoku(board):
                return True
            board[r][c] = 0
    return False