Solving Sudoku with Python

TL;DR: Sudoku can be solved efficiently with a recursive backtracking algorithm. Below is a clean Python implementation you can run locally, plus tips to make it faster.

What is the approach?

We use backtracking: try filling an empty cell with a valid candidate (1–9), recurse; if the choice leads to contradiction later, undo and try the next candidate. This brute-force method is simple and fast enough for typical puzzles when combined with good ordering / checks.

Python solver (copy & run)

Save as sudoku_solver.py and run. This uses plain Python (no external libraries).

# Sudoku solver using backtracking
from typing import List, Tuple, Optional

Grid = List[List[int]]

def find_empty(grid: Grid) -> Optional[Tuple[int,int]]:
    """Return row, col of first empty cell (0)."""
    for r in range(9):
        for c in range(9):
            if grid[r][c] == 0:
                return r, c
    return None

def is_valid(grid: Grid, row: int, col: int, val: int) -> bool:
    """Check if placing val at (row,col) is valid per Sudoku rules."""
    # Row/col check
    if any(grid[row][j] == val for j in range(9)):
        return False
    if any(grid[i][col] == val for i in range(9)):
        return False
    # 3x3 block check
    br, bc = 3 * (row // 3), 3 * (col // 3)
    for i in range(br, br + 3):
        for j in range(bc, bc + 3):
            if grid[i][j] == val:
                return False
    return True

def solve_sudoku(grid: Grid) -> bool:
    """Solve sudoku in-place. Return True if solved."""
    empty = find_empty(grid)
    if not empty:
        return True  # solved
    r, c = empty
    for val in range(1, 10):
        if is_valid(grid, r, c, val):
            grid[r][c] = val
            if solve_sudoku(grid):
                return True
            grid[r][c] = 0  # backtrack
    return False

def print_grid(grid: Grid) -> None:
    for i, row in enumerate(grid):
        line = ' '.join(str(n) if n != 0 else '.' for n in row)
        print(line)
    print()

# Example puzzle (0 indicates empty)
puzzle = [
 [5,3,0, 0,7,0, 0,0,0],
 [6,0,0, 1,9,5, 0,0,0],
 [0,9,8, 0,0,0, 0,6,0],
 [8,0,0, 0,6,0, 0,0,3],
 [4,0,0, 8,0,3, 0,0,1],
 [7,0,0, 0,2,0, 0,0,6],
 [0,6,0, 0,0,0, 2,8,0],
 [0,0,0, 4,1,9, 0,0,5],
 [0,0,0, 0,8,0, 0,7,9]
]

print("Puzzle:")
print_grid(puzzle)
if solve_sudoku(puzzle):
    print("Solved:")
    print_grid(puzzle)
else:
    print("No solution found.")

Example output

Running the script above prints the puzzle and the solved grid. The solver fills the board in-place and prints the final solution.

Optimizations & Tips

• Cell ordering: pick the empty cell with the fewest candidates (minimum remaining value heuristic) — dramatically reduces branching.
• Precompute candidates: maintain row/col/block sets so is_valid is O(1).
• Constraint propagation: apply deterministic fills first (naked singles) before backtracking.
• Use bitmasks: bit operations speed up candidate checks if you need performance for many puzzles.

Complexity

Worst-case complexity is high (exponential), but real Sudoku puzzles are designed to have unique solutions and can be solved quickly by backtracking with heuristics. Typical solver finishes in milliseconds for common puzzles.

Visual embed (optional)

You can display a small HTML table version of the starting puzzle on your blog. Example markup (static):

Beyond backtracking

If you enjoy puzzles, try these next steps:

1. Implement the MRV (minimum remaining values) heuristic + forward checking.
2. Build a simple web UI (HTML/JS) to input puzzles and call the Python solver via an API (Flask/Streamlit).
3. Compare constraint programming libraries (e.g., OR-Tools CP-SAT solver) for elegant constraint-based solutions.