Sudoku Solver

Fill a 9×9 Sudoku grid so every row, column, and 3×3 box contains digits 1–9 exactly once. The standard backtracking approach finds the next empty cell, tries digits 1–9, and uses constraint pruning via an isValid check. This lesson covers the algorithm, LeetCode 37, and implementations in C, Java, and Python with trace tables.

Overview

Sudoku is a classic constraint satisfaction problem (CSP). Each empty cell has up to nine choices, but row, column, and box rules eliminate most candidates early — exactly what backtracking pruning is designed for.

9×9 grid — three constraint groups per placement

  Row:    each digit 1–9 appears once
  Column: each digit 1–9 appears once
  Box:    each 3×3 subgrid has digits 1–9 once

Backtrack: find empty → try digit → isValid? → recurse or undo

Problem Statement

Input: A 9×9 board where '.' marks empty cells and digits '1'…'9' are fixed clues.

Output: Fill all empty cells so the board is valid. LeetCode 37 guarantees exactly one solution.

Rules:

• Each row contains digits 1–9 without repetition.
• Each column contains digits 1–9 without repetition.
• Each of the nine 3×3 sub-boxes contains digits 1–9 without repetition.

Backtracking Algorithm

1. Scan the board for the first empty cell (row, col).
2. If no empty cell exists, the puzzle is solved — return true.
3. For each digit 1 … 9:
   • If isValid(board, row, col, digit), place the digit.
   • Recurse to fill remaining cells.
   • If recursion succeeds, propagate true.
   • Otherwise backtrack: reset cell to '.'.
4. If no digit works, return false (trigger backtrack at caller).

The isValid Check

Before placing digit at (row, col), verify it does not conflict with existing values in:

• Same row: scan all columns in row
• Same column: scan all rows in col
• Same 3×3 box: scan rows boxRow … boxRow+2, cols boxCol … boxCol+2 where boxRow = (row/3)*3, boxCol = (col/3)*3

Optimized variant: Maintain boolean arrays (or bitmasks) for rows, columns, and boxes to test validity in O(1) and update them on place/undo.

Code (C, Java, Python)

Python

def is_valid(board, row, col, digit):
    """Constraint check: row, column, and 3×3 box."""
    for c in range(9):
        if board[row][c] == digit:
            return False
    for r in range(9):
        if board[r][col] == digit:
            return False
    box_row, box_col = (row // 3) * 3, (col // 3) * 3
    for r in range(box_row, box_row + 3):
        for c in range(box_col, box_col + 3):
            if board[r][c] == digit:
                return False
    return True


def solve_sudoku(board):
    """Backtracking: fill next empty cell or return True when done."""
    for row in range(9):
        for col in range(9):
            if board[row][col] != '.':
                continue
            for digit in '123456789':
                if not is_valid(board, row, col, digit):
                    continue
                board[row][col] = digit
                if solve_sudoku(board):
                    return True
                board[row][col] = '.'
            return False
    return True


if __name__ == "__main__":
    grid = [
        list("53..7...."),
        list("6..195..."),
        list(".98....6."),
        list("8..6...3."),
        list("4..8.3..1"),
        list("7..2...6."),
        list(".6....28."),
        list("..419...."),
        list("....8..79"),
    ]
    solve_sudoku(grid)
    print(''.join(''.join(r) for r in grid))

Java

public class SudokuSolver {

    private static boolean isValid(char[][] board, int row, int col, char digit) {
        for (int c = 0; c < 9; c++)
            if (board[row][c] == digit) return false;
        for (int r = 0; r < 9; r++)
            if (board[r][col] == digit) return false;
        int boxRow = (row / 3) * 3, boxCol = (col / 3) * 3;
        for (int r = boxRow; r < boxRow + 3; r++)
            for (int c = boxCol; c < boxCol + 3; c++)
                if (board[r][c] == digit) return false;
        return true;
    }

    public static boolean solve(char[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] != '.') continue;
                for (char digit = '1'; digit <= '9'; digit++) {
                    if (!isValid(board, row, col, digit)) continue;
                    board[row][col] = digit;
                    if (solve(board)) return true;
                    board[row][col] = '.';
                }
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
            "53..7....".toCharArray(),
            "6..195...".toCharArray(),
            ".98....6.".toCharArray()
        };
        /* extend to full 9×9 board in practice */
    }
}

C

#include <stdio.h>
#include <stdbool.h>

bool is_valid(char board[9][9], int row, int col, char digit) {
    int c, r;
    int box_row = (row / 3) * 3, box_col = (col / 3) * 3;
    for (c = 0; c < 9; c++)
        if (board[row][c] == digit) return false;
    for (r = 0; r < 9; r++)
        if (board[r][col] == digit) return false;
    for (r = box_row; r < box_row + 3; r++)
        for (c = box_col; c < box_col + 3; c++)
            if (board[r][c] == digit) return false;
    return true;
}

bool solve_sudoku(char board[9][9]) {
    int row, col, d;
    for (row = 0; row < 9; row++) {
        for (col = 0; col < 9; col++) {
            if (board[row][col] != '.') continue;
            for (d = '1'; d <= '9'; d++) {
                if (!is_valid(board, row, col, (char)d)) continue;
                board[row][col] = (char)d;
                if (solve_sudoku(board)) return true;
                board[row][col] = '.';
            }
            return false;
        }
    }
    return true;
}

Output & Trace

Sample puzzle (input)

53..7....
6..195...
.98....6.
8..6...3.
4..8.3..1
7..2...6.
.6....28.
..419....
....8..79

First empty cell — partial trace at (0, 2)

Solved board (output)

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Constraint groups checked per placement

LeetCode 37 & 36

Optimizations

• Candidate sets: Precompute valid digits per empty cell to skip invalid tries.
• MRV heuristic: Pick the empty cell with fewest candidates first — reduces branching.
• Bitmask tracking: Use 9-bit masks for rows, columns, and boxes for O(1) checks.
• Forward checking: Remove candidates from neighbors when placing a digit.

Approach Comparison

Real-Life Applications

Interview Tips

1. Clarify: modify board in-place; return when all cells filled.
2. Write isValid as a separate function — row, column, box loops.
3. Box origin: (row/3)*3 and (col/3)*3 — say this out loud.
4. Backtrack explicitly: reset cell to '.' when recursion fails.
5. Mention LC 36 if asked how to validate without solving.
6. Connect to N-Queens and pruning techniques.