Sudoku Solver - Learning Module

Loading content...

0/276

Cell-by-Cell Exploration

The Art of Systematic Exploration

At the heart of every Sudoku-solving algorithm lies a deceptively simple question: which cell should I fill next? This question, answered wisely, can mean the difference between solving a puzzle in microseconds versus minutes—or not at all.

Cell-by-cell exploration is the process of systematically visiting each empty cell in the puzzle, attempting valid values, and recursively proceeding until either a solution is found or all possibilities are exhausted. While the high-level description sounds straightforward, the implementation details profoundly impact performance.

What You Will Learn

This page dives deep into cell-by-cell exploration strategies. You'll learn how to traverse the puzzle grid, understand why traversal order matters, master the Minimum Remaining Values (MRV) heuristic that dramatically improves performance, and see how recursion structures the search.

The Exploration Problem

When facing a partially filled Sudoku grid, we must decide how to navigate through the empty cells. This is not a trivial decision—the order in which we explore cells fundamentally shapes the search tree we traverse.

The basic setup:

Given a puzzle with N empty cells, we need to:

Choose which empty cell to fill first
Try valid values for that cell
For each choice, recursively solve the remaining puzzle with N-1 empty cells
Backtrack if we hit a dead end

This recursive structure creates a search tree where:

Each node represents a partial puzzle state
Each branch represents trying a specific value for the current cell
Leaves are either complete solutions or contradictions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                            [Initial Puzzle: 56 empty cells]
                                        |
                    Choose first empty cell (e.g., cell A)
                            /           |           \
                         A=1          A=2          A=8
                          |            |            |
              [55 empty cells]  [55 empty cells]  [55 empty cells]
                    |                  |                |
        Choose second empty cell (e.g., cell B)
               / | \              / | \            / | \
             B=1 B=3 B=7       B=2 B=4 B=9      B=1 B=5 B=6
              |   |   |         |   |   |        |   |   |
            ...  ...  ...     ...  ...  ...    ...  ...  ...
 
Each path from root to leaf represents a sequence of decisions.
Solutions are valid leaves. Dead ends (constraint violations) 
trigger backtracking up the tree.

Why cell order matters:

Consider two extreme strategies:

Strategy A: Choose cells left-to-right, top-to-bottom (row-major order) Strategy B: Choose the cell with fewest remaining valid values (MRV heuristic)

With Strategy A, you might start with a cell that has 8 valid options, creating 8 branches at the first level. Each of those branches might also have many options. The tree grows wide quickly.

With Strategy B, if there's a cell with only 1 valid option—that's a forced move. No branching needed. If the narrowest cell has 2 options, you have only 2 branches. The tree stays narrow.

Narrow trees are exponentially smaller than wide trees. If your first decision has 2 vs 8 options, and this pattern continues, you might explore 2⁵⁰ vs 8⁵⁰ nodes—a difference of approximately 10¹⁵ vs 10⁴⁵. That's 10³⁰ times more work for the wider tree!

The Explosion Problem

Poor cell ordering doesn't just slow things down—it can make problems unsolvable in practice. A branching factor of 5 for 50 decisions means 5⁵⁰ ≈ 10³⁵ nodes. Even at a billion nodes per second, that's 10²⁶ seconds—longer than the age of the universe. Good ordering is not optional.

Basic Traversal Strategies

Let's start with the simplest approaches and understand their characteristics before moving to more sophisticated strategies.

Simple Traversal Orders

•Row-Major Order: Scan cells left-to-right, top-to-bottom. Skip filled cells. The simplest approach—requires no analysis, just iteration.
•Column-Major Order: Scan cells top-to-bottom, left-to-right. Equivalent to row-major in most respects; no inherent advantage.
•Snake Order: Alternate direction each row (left-to-right, then right-to-left). Slightly improves cache locality but no algorithmic benefit.
•Diagonal Order: Traverse diagonally. Can catch certain constraint propagation patterns slightly earlier, but minimal practical impact.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def find_next_empty_cell_linear(board):
    """
    Find the next empty cell using row-major (linear) order.
    Returns (row, col) tuple or None if board is complete.
    
    Time: O(81) worst case per call = O(1) since grid is fixed size
    """
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:  # 0 indicates empty
                return (row, col)
    return None  # No empty cells - puzzle is complete
 
def solve_sudoku_linear(board):
    """Backtracking solver using linear cell selection."""
    cell = find_next_empty_cell_linear(board)
    
    if cell is None:
        return True  # Solved!
    
    row, col = cell
    
    for num in range(1, 10):  # Try digits 1-9
        if is_valid_placement(board, row, col, num):
            board[row][col] = num
            
            if solve_sudoku_linear(board):
                return True
            
            board[row][col] = 0  # Backtrack
    
    return False  # No valid digit found - backtrack

Analysis of linear traversal:

Pros:

Simple to implement
Predictable memory access pattern (good for CPU cache)
No overhead for cell selection analysis

Cons:

Ignores problem structure entirely
May start with highly unconstrained cells (many options)
Can build deep trees before discovering contradictions
Performance varies wildly with puzzle layout

Linear traversal treats all empty cells as equally important. But they're not—some cells are heavily constrained (few valid options) while others are loosely constrained (many options). A cell with only one valid option requires no guessing; we should handle these first.

When Linear Works

Linear traversal is acceptable for very easy puzzles where constraint propagation alone solves most cells, leaving few branching decisions. It's also useful as a baseline for understanding how much smarter heuristics help. But for any serious Sudoku solver, we need better strategies.

The Minimum Remaining Values (MRV) Heuristic

The Minimum Remaining Values (MRV) heuristic, also called the "Most Constrained Variable" or "Fail-First" heuristic, is the single most important improvement to naïve backtracking. The idea is brilliantly simple:

Always choose the empty cell with the fewest legal values remaining.

This strategy is called "fail-first" because if we're going to fail (hit a dead end), we want to discover it as soon as possible. Cells with few options are most likely to lead to contradictions quickly, either because:

We guess wrong and discover the contradiction immediately
We guess right and propagation dramatically simplifies the puzzle

Either outcome is good—we either prune early or make rapid progress.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def find_next_cell_mrv(board, domains):
    """
    Find the empty cell with Minimum Remaining Values (MRV).
    
    Args:
        board: Current puzzle state (0 = empty)
        domains: 9x9 array of sets, domains[r][c] = possible values for cell (r,c)
    
    Returns:
        (row, col) of cell with fewest remaining options, or None if complete
    
    Time: O(81) = O(1) to scan all cells
    """
    min_values = 10  # Sentinel value (max possible is 9)
    best_cell = None
    
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:  # Empty cell
                num_values = len(domains[row][col])
                
                if num_values == 0:
                    # Cell has no valid values - early failure detection
                    return (-1, -1)  # Signal contradiction
                
                if num_values == 1:
                    # Cell is forced (naked single) - process immediately
                    return (row, col)
                
                if num_values < min_values:
                    min_values = num_values
                    best_cell = (row, col)
    
    return best_cell
 
def solve_sudoku_mrv(board, domains):
    """Backtracking solver using MRV heuristic."""
    cell = find_next_cell_mrv(board, domains)
    
    if cell is None:
        return True  # All cells filled - solution found!
    
    row, col = cell
    
    if row == -1:
        return False  # Contradiction detected during cell selection
    
    # Try each value in the cell's domain
    for num in domains[row][col].copy():  # Copy because we'll modify domains
        # Tentative assignment
        board[row][col] = num
        old_domains = deep_copy(domains)  # Save state for backtracking
        domains[row][col] = {num}
        
        # Propagate constraints
        if propagate_constraints(board, domains, row, col, num):
            if solve_sudoku_mrv(board, domains):
                return True
        
        # Backtrack
        board[row][col] = 0
        domains = restore_domains(old_domains)  # Restore saved state
    
    return False

Why MRV works so well:

Consider the search tree impact. With linear ordering, your first cell might have 7 possible values, creating 7 branches. With MRV, if there exists a cell with only 2 values, you start with only 2 branches.

The effect compounds: at each level of recursion, MRV picks the narrowest point. The resulting search tree is typically much smaller.

Mathematical intuition:

Let's say each cell has bi options when selected. The total work is roughly b₁ × b₂ × b₃ × ... × bₙ. This product is minimized when we select cells with smaller bi values first—and MRV does exactly that at each step.

Moreover, cells with small domains often become forced (singleton domains) after constraint propagation, eliminating branching entirely. MRV naturally prioritizes these cells, converting branching nodes into linear progress.

MRV Performance Impact (Typical Puzzles)
Puzzle Difficulty	Nodes with Linear	Nodes with MRV	Speedup
Easy	~50-200	~10-30	5-10×
Medium	~500-2,000	~30-100	15-30×
Hard	~5,000-50,000	~100-500	50-100×
Evil/Expert	~100,000-1,000,000	~500-5,000	100-200×

Fail Fast, Win Fast

MRV embodies a profound algorithmic principle: position yourself to fail quickly. Early failures mean early backtracking, which means avoiding exponentially large subtrees. Paradoxically, eagerly seeking failure leads to faster success.

Domain Tracking and Management

MRV requires knowing how many values remain valid for each cell—this requires domain tracking. Efficient domain management is crucial for both MRV performance and constraint propagation.

Domain representation strategies:

We need a data structure that supports:

Checking if a value is in a cell's domain: O(1)
Removing a value from a domain: O(1)
Counting remaining values: O(1)
Copying/restoring domains for backtracking: efficient

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# Option 1: Sets (Simple and Clear)
# Pros: Operations are intuitive, set operations available
# Cons: Copying is O(k) where k is domain size; memory overhead
domains = [[set(range(1, 10)) for _ in range(9)] for _ in range(9)]
domains[0][0].remove(5)           # O(1) remove
value in domains[0][0]             # O(1) membership
len(domains[0][0])                 # O(1) size
 
# Option 2: Bitsets (Highly Efficient)
# Using a 16-bit integer where bit i represents whether value i is in domain
# Pros: O(1) copy, extremely cache-friendly, fast operations
# Cons: Slightly less intuitive, limited to small domains
class BitsetDomain:
    def __init__(self):
        self.bits = 0b111111111 << 1  # Bits 1-9 set (ignore bit 0)
    
    def remove(self, value):
        self.bits &= ~(1 << value)  # Clear bit
    
    def contains(self, value):
        return bool(self.bits & (1 << value))
    
    def count(self):
        return bin(self.bits).count('1')  # Population count
    
    def copy(self):
        new_domain = BitsetDomain()
        new_domain.bits = self.bits  # O(1) copy!
        return new_domain
    
    def values(self):
        # Iterate over set bits
        for val in range(1, 10):
            if self.bits & (1 << val):
                yield val
 
# Example usage:
domain = BitsetDomain()
domain.remove(3)
domain.remove(7)
print(domain.count())  # 7
print(list(domain.values()))  # [1, 2, 4, 5, 6, 8, 9]

Backtracking and domain restoration:

When we try a value and later backtrack, we must restore domains to their previous state. There are two main strategies:

Strategy 1: Copy-on-branch

Before making a choice, deep-copy all domains
Modify the copy during exploration
On backtrack, discard modified copy and revert to saved copy
Pros: Conceptually simple, restoration is O(1)
Cons: Copying 81 domains is O(81) = O(1) but has constant overhead

Strategy 2: Trail-based undo

Record each domain modification as (row, col, value_removed)
On backtrack, replay the trail in reverse, re-adding values
Pros: Only records actual changes (often fewer than 81)
Cons: More complex bookkeeping, must maintain trail stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class SudokuSolverWithTrail:
    def __init__(self, puzzle):
        self.board = [row[:] for row in puzzle]
        self.domains = [[set(range(1, 10)) for _ in range(9)] for _ in range(9)]
        self.trail = []  # Stack of (row, col, value) tuples
        self.trail_markers = []  # Markers for backtracking levels
        self.initialize_domains()
    
    def mark_trail(self):
        """Save current trail position before making a choice."""
        self.trail_markers.append(len(self.trail))
    
    def restore_trail(self):
        """Undo all domain changes since the last mark."""
        if not self.trail_markers:
            return
        
        restore_point = self.trail_markers.pop()
        
        while len(self.trail) > restore_point:
            row, col, value = self.trail.pop()
            self.domains[row][col].add(value)
    
    def remove_from_domain(self, row, col, value):
        """Remove value from domain and record in trail."""
        if value in self.domains[row][col]:
            self.domains[row][col].remove(value)
            self.trail.append((row, col, value))
            return True
        return False
    
    def solve(self):
        cell = self.find_mrv_cell()
        if cell is None:
            return True
        
        row, col = cell
        if len(self.domains[row][col]) == 0:
            return False
        
        for value in list(self.domains[row][col]):
            self.mark_trail()  # Save state
            
            self.board[row][col] = value
            self.domains[row][col] = {value}
            
            if self.propagate(row, col, value) and self.solve():
                return True
            
            self.board[row][col] = 0
            self.restore_trail()  # Undo domain changes
        
        return False

Performance Consideration

For Sudoku's fixed 9×9 size, either strategy works well. Bitset domains with copy-on-branch are fastest for this size—copying 81 integers is trivial. For larger constraints (16×16 Sudoku, general CSPs), trail-based undo becomes more attractive as copying costs grow.

The Recursive Structure of Search

Backtracking Sudoku solvers are fundamentally recursive algorithms. Understanding the recursive structure is essential for implementing, debugging, and optimizing solvers.

The recursive pattern:

At each recursive call, we're solving a smaller subproblem: the remaining puzzle after some cells have been filled. The recursive structure mirrors the search tree—each call corresponds to a node, and each recursive call to a child node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def solve(board, domains, depth=0):
    """
    Recursive backtracking solver with detailed structure.
    
    The function represents exploring one node of the search tree.
    'depth' tracks how deep we are in the tree (for debugging/analysis).
    """
    # STEP 1: Base case - Check if we're done
    cell = find_mrv_cell(board, domains)
    if cell is None:
        # All cells filled successfully
        print(f"Solution found at depth {depth}")
        return True
    
    row, col = cell
    
    # STEP 2: Check for immediate failure (fail-fast)
    if len(domains[row][col]) == 0:
        # No valid values for this cell - dead end
        return False
    
    # STEP 3: Branching - try each value in domain
    for value in sorted(domains[row][col]):  # Sorting for determinism
        # This creates a new branch in the search tree
        
        # STEP 4: Make a tentative choice
        saved_board_cell = board[row][col]
        saved_domains = deep_copy(domains)
        
        board[row][col] = value
        domains[row][col] = {value}
        
        # STEP 5: Propagate constraints (prune search space)
        propagation_success = propagate_constraints(board, domains, row, col, value)
        
        if propagation_success:
            # STEP 6: Recursive call - explore this branch
            if solve(board, domains, depth + 1):
                return True  # Solution found in this subtree
        
        # STEP 7: Backtrack - undo the tentative choice
        board[row][col] = saved_board_cell
        domains = restore_from(saved_domains)
        
        # Continue to next value in the loop
    
    # STEP 8: All values tried, none worked - report failure upward
    return False

Understanding the call stack:

The recursion depth corresponds to the number of guesses (branching decisions) made. In the worst case, this equals the number of empty cells. For a puzzle with 56 empty cells, the maximum stack depth is 56—well within default stack limits.

Key recursive properties:

Base cases:
- Success: No empty cells remain → return True
- Failure: A cell has no valid values → return False
Recursive case: For each value in the current cell's domain:
- Try the value
- Recursively solve the rest
- If successful, return True
- If failed, backtrack and try next value
Backtracking guarantee: If we return False, the board is restored to its state before the call. This invariant ensures correct exploration.

Recursive Thinking

The power of recursion is that each call handles just one decision, delegating the rest to recursive calls. You don't need to think about all 56 empty cells at once—just focus on the current cell and trust that recursion will handle the rest. This decomposition makes the algorithm both elegant and correct.

Iterative Implementation with Explicit Stack

While recursion is natural for backtracking, some situations call for an iterative implementation using an explicit stack. Reasons include:

Stack depth limits: Some languages have shallow recursion limits
Performance: Avoiding function call overhead
State inspection: Easier to examine/modify the search history
Parallelization: Explicit stacks are easier to partition for parallel search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def solve_iterative(board):
    """
    Iterative backtracking using explicit stack.
    
    Stack items: (cell_index, value_index)
      - cell_index: which empty cell we're working on (0 to num_empty-1)
      - value_index: which value in the domain we're trying (0 to len(domain)-1)
    """
    # Preprocessing: collect empty cells and compute initial domains
    empty_cells = []
    domains = [[set(range(1, 10)) for _ in range(9)] for _ in range(9)]
    
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                empty_cells.append((r, c))
            else:
                # Update domains based on initial values
                update_domains_for_placement(domains, r, c, board[r][c])
    
    # Sort cells by MRV (static ordering - could be dynamic)
    empty_cells.sort(key=lambda cell: len(domains[cell[0]][cell[1]]))
    
    # Initialize stack
    stack = []  # Each entry: (cell_idx, value_idx, saved_domains)
    cell_idx = 0
    value_idx = 0
    
    while True:
        if cell_idx == len(empty_cells):
            # All cells filled - solution found!
            return True
        
        row, col = empty_cells[cell_idx]
        domain_values = list(domains[row][col])
        
        if value_idx >= len(domain_values):
            # Exhausted all values for this cell - backtrack
            if not stack:
                return False  # No more options - puzzle unsolvable
            
            # Pop previous state
            board[row][col] = 0
            cell_idx, value_idx, domains = stack.pop()
            value_idx += 1  # Try next value at previous level
            row, col = empty_cells[cell_idx]
            board[row][col] = 0
            continue
        
        # Try current value
        value = domain_values[value_idx]
        
        if is_valid_placement(board, row, col, value):
            # Save state and make placement
            stack.append((cell_idx, value_idx, deep_copy(domains)))
            board[row][col] = value
            update_domains_for_placement(domains, row, col, value)
            
            # Move to next cell
            cell_idx += 1
            value_idx = 0
        else:
            # Value invalid, try next
            value_idx += 1

Recursive Approach

•Natural expression of backtracking
•Cleaner code and easier to understand
•Implicit state management via call stack
•Good for prototyping and clarity

Iterative Approach

•No stack overflow risk
•Slightly faster (no call overhead)
•Explicit state enables inspection
•Better for parallelization

When to choose each approach:

For Sudoku specifically, recursion depth is at most 81 (and typically much less), so stack overflow is not a concern in most languages. The recursive approach is therefore usually preferred for clarity.

However, if you're building a high-performance solver, implementing advanced techniques like work-stealing parallelism, or working in a language with severe stack limits, the iterative approach becomes necessary.

Advanced Cell Selection Strategies

MRV is powerful, but it can be enhanced or combined with other heuristics for even better performance:

Beyond Basic MRV

•Tie-Breaking with Degree Heuristic: When multiple cells have the same minimum domain size, choose the one involved in the most constraints with unassigned cells. This cell's assignment will propagate most widely.
•Dynamic MRV: Recompute domains after each propagation step, always selecting the globally tightest cell. More accurate but more expensive.
•Watched Literals: Track when domains shrink to specific sizes, triggering immediate processing without scanning all cells.
•Constraint Propagation Priority: Process forced cells (singleton domains) immediately, in a BFS/DFS from the most recently assigned cell, before considering guesses.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def find_cell_mrv_with_degree(board, domains):
    """
    MRV heuristic with degree tie-breaking.
    
    Primary: Minimum Remaining Values (fewer options = higher priority)
    Secondary: Maximum Degree (more unassigned peers = higher priority)
    """
    best_cell = None
    min_values = 10
    max_degree = -1
    
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                num_values = len(domains[row][col])
                
                if num_values == 0:
                    return (-1, -1)  # Contradiction
                
                if num_values == 1:
                    return (row, col)  # Forced - process immediately
                
                # Compute degree: number of unassigned peers
                degree = count_unassigned_peers(board, row, col)
                
                # Compare: prioritize fewer values, break ties by more degree
                if (num_values < min_values or 
                    (num_values == min_values and degree > max_degree)):
                    min_values = num_values
                    max_degree = degree
                    best_cell = (row, col)
    
    return best_cell
 
def count_unassigned_peers(board, row, col):
    """Count empty cells that share a unit with (row, col)."""
    count = 0
    peers = get_peers(row, col)  # Row, column, and box peers
    
    for peer_row, peer_col in peers:
        if board[peer_row][peer_col] == 0:
            count += 1
    
    return count

Constraint propagation queues:

An advanced technique is to maintain a propagation queue of cells whose domains have recently changed. After each assignment, rather than immediately selecting the next cell, process this queue first:

Assign a value to a cell
For each affected peer, check if domain became singleton → add to queue
While queue is non-empty:
- Pop a cell
- If singleton, assign its forced value
- Propagate and add new singletons to queue
Only after queue is empty, apply MRV for next guess

This ensures we extract maximum value from each guess before making another, often solving large portions 'for free' without branching.

Propagation First, Guessing Last

The most efficient solvers treat guessing as a last resort. Every forced deduction (naked single, hidden single) should be made before any branching occurs. The MRV heuristic itself encourages this—singleton domains are prioritized—but explicit queue-based propagation makes it systematic.

Summary: Mastering Cell-by-Cell Exploration

We've thoroughly explored the strategies for navigating Sudoku puzzles cell by cell. Let's consolidate the key insights:

Key Takeaways

•Cell order dramatically impacts performance — choosing cells wisely can reduce search tree size by factors of millions.
•MRV (Minimum Remaining Values) is the single most important heuristic — always choose the most constrained cell first.
•Fail-fast principle — detecting dead ends early through MRV and propagation avoids exponential subtrees.
•Domain tracking is essential for MRV — use sets or bitsets to efficiently maintain possible values per cell.
•Recursive structure naturally models backtracking — each call handles one decision, trusting recursion for the rest.
•Iterative alternative with explicit stack enables advanced techniques but is rarely necessary for Sudoku's modest depth.
•Propagation before guessing — exhaust all forced moves before branching.

Looking Ahead

We've established how to navigate through cells and when to choose which cell. The next critical question is: how do we know if a value placement is valid? The next page dives deep into validity checking—the constraint enforcement that determines whether our choices lead to solutions or contradictions.

The navigation framework:

Think of cell-by-cell exploration as the GPS for our search. MRV tells us where to go next (the most constrained cell). Propagation fills in obvious steps automatically (forced moves). Backtracking reroutes when we hit dead ends. Together, they form a navigation system that explores the vast search space efficiently, always pruning aggressively and advancing purposefully.