Constraint Satisfaction in Sudoku - Sudoku Solver — Backtracking in Action | OneNoughtOne

0/361

Data Structures & AlgorithmsBacktracking

Sudoku Solver — Backtracking in Action

LevelIntermediate

Duration60 mins

TopicBacktracking

1 / 4

Constraint Satisfaction in Sudoku

The Perfect Backtracking Laboratory

Sudoku is more than a popular puzzle game—it is a masterclass in constraint satisfaction and backtracking. When you solve a Sudoku puzzle by hand, your brain naturally engages in pattern recognition, constraint propagation, and when stuck, trial-and-error with backtracking. This cognitive process mirrors precisely what we must teach a computer to do algorithmically.

Unlike many toy backtracking problems, Sudoku possesses a unique property: it is simple enough to understand in seconds, yet complex enough to challenge the world's fastest algorithms. A standard 9×9 Sudoku grid has approximately 6.67 × 10²¹ possible configurations to explore naively—a number so astronomical that brute force is utterly infeasible. Yet, through clever constraint satisfaction techniques combined with intelligent backtracking, we can solve most puzzles in milliseconds.

What You Will Learn

By the end of this page, you will understand Sudoku as a Constraint Satisfaction Problem (CSP)—a formal framework that structures how we think about puzzle-solving. You'll learn the three fundamental components of any CSP (variables, domains, and constraints), and see how this framework directly guides the design of efficient backtracking algorithms. This understanding transfers far beyond Sudoku to scheduling, resource allocation, circuit design, and countless other domains.

What Is a Constraint Satisfaction Problem?

Before diving into Sudoku-specific details, we must understand the general framework that underlies all constraint-based puzzle solving. A Constraint Satisfaction Problem (CSP) is defined by three components:

1. Variables (X): A set of entities that need to be assigned values. In Sudoku, each empty cell is a variable—something we need to determine.

2. Domains (D): For each variable, a set of possible values it can take. In Sudoku, each cell's domain is initially {1, 2, 3, 4, 5, 6, 7, 8, 9}, though pre-filled cells have singleton domains containing only their given value.

3. Constraints (C): Rules that restrict which combinations of values are valid. Sudoku has three constraint types: row uniqueness, column uniqueness, and 3×3 box uniqueness.

A solution to a CSP is an assignment of values to all variables such that every constraint is satisfied simultaneously. A CSP may have zero solutions (inconsistent), exactly one solution (well-posed), or multiple solutions.

Constraint Satisfaction Problem (CSP) = <X, D, C>
 
Where:
  X = {x₁, x₂, ..., xₙ}           // Set of n variables
  D = {D₁, D₂, ..., Dₙ}           // Domain for each variable
  C = {C₁, C₂, ..., Cₘ}           // Set of m constraints
 
Each constraint Cⱼ involves a subset of variables and specifies
the allowable combinations of values for those variables.
 
SOLUTION: An assignment {x₁=v₁, x₂=v₂, ..., xₙ=vₙ} where:
  - vᵢ ∈ Dᵢ for all i (each value is from the correct domain)
  - All constraints C₁, C₂, ..., Cₘ are satisfied

Why CSP Formalization Matters

The CSP framework isn't just academic notation—it's a thinking tool. By explicitly identifying variables, domains, and constraints, you transform a fuzzy problem description into a structured specification that directly informs your algorithm. Every backtracking solver, at its core, systematically explores variable assignments while checking constraint satisfaction.

The CSP perspective transforms problem-solving:

Without CSP thinking, Sudoku seems like a puzzle requiring clever insights. With CSP thinking, Sudoku becomes a systematic search problem with well-defined structure. This shift—from intuition to formalism—is what enables us to write algorithms that solve puzzles deterministically.

The power of CSP lies in its generality. Once you understand how to solve CSPs, you can apply the same techniques to:

Graph coloring: Variables = vertices, domains = colors, constraints = adjacent vertices differ
Scheduling: Variables = time slots, domains = possible times, constraints = resource conflicts
Circuit layout: Variables = component positions, domains = grid locations, constraints = no overlaps
Sudoku: Variables = cells, domains = {1-9}, constraints = row/column/box uniqueness

Sudoku as a Constraint Satisfaction Problem

Let's now formalize Sudoku precisely within the CSP framework. A standard 9×9 Sudoku puzzle has the following structure:

Sudoku CSP Components

•Variables (X): 81 cells, denoted X[r][c] for row r ∈ {0,1,...,8} and column c ∈ {0,1,...,8}. Each cell is a variable that must receive exactly one value.
•Domains (D): For empty cells, D[r][c] = {1, 2, 3, 4, 5, 6, 7, 8, 9}. For pre-filled cells with given value v, D[r][c] = {v}—a singleton domain enforcing the given clue.
•Row Constraints: For each row r, all cells X[r][0], X[r][1], ..., X[r][8] must have distinct values. This gives 9 all-different constraints, one per row.
•Column Constraints: For each column c, all cells X[0][c], X[1][c], ..., X[8][c] must have distinct values. Another 9 all-different constraints.
•Box Constraints: For each of the 9 non-overlapping 3×3 boxes, all 9 cells within must have distinct values. Another 9 all-different constraints.

SUDOKU CSP = <X, D, C>
 
VARIABLES:
  X = { X[r][c] | r ∈ {0..8}, c ∈ {0..8} }
  Total: 81 variables
 
DOMAINS:
  If cell (r,c) is given value v: D[r][c] = {v}
  If cell (r,c) is empty:         D[r][c] = {1,2,3,4,5,6,7,8,9}
 
CONSTRAINTS (27 total):
  Row constraints (9):
    ∀r: AllDifferent(X[r][0], X[r][1], ..., X[r][8])
  
  Column constraints (9):
    ∀c: AllDifferent(X[0][c], X[1][c], ..., X[8][c])
  
  Box constraints (9):
    For each 3×3 box starting at (boxRow, boxCol):
      AllDifferent(all 9 cells in the box)
 
Where AllDifferent(v₁, v₂, ..., vₖ) means:
  ∀i,j where i ≠ j: vᵢ ≠ vⱼ

Constraint density and hardness:

Sudoku is a densely constrained CSP. Each cell participates in exactly 3 constraints (its row, its column, and its box), but more importantly, each cell is constrained by 20 other cells (8 in its row + 8 in its column + 4 additional in its box, avoiding double-counting). This high degree of interconnection is what makes Sudoku interesting—every decision has widespread implications.

The interconnected nature of Sudoku constraints creates cascading effects. When you place a number in a cell, you immediately eliminate that number from the domains of 20 other cells. This domain reduction can trigger further reductions (if a cell's domain becomes a singleton, that's a forced move), potentially solving large portions of the puzzle through constraint propagation alone.

Sudoku Constraint Relationships
Cell's Constraint Scope	Count	Description
Row peers	8	All other cells in the same row
Column peers	8	All other cells in the same column
Box peers (excluding row/column overlap)	4	Other cells in the 3×3 box not already counted
Total peers	20	Total cells that constrain any given cell

The Search Space Perspective

Understanding Sudoku as a CSP reveals the astronomical search space we're navigating. Let's analyze the scale of the problem:

Naïve upper bound: If we ignore all constraints and simply try every possible digit in every cell, we have 9 choices for each of 81 cells, giving 9⁸¹ ≈ 10⁷⁷ possible configurations. This exceeds the number of atoms in the observable universe by roughly 10⁷⁷/10⁸⁰ = a meaningful fraction.

Actual solution space: Accounting for Sudoku's constraints, there are exactly 6,670,903,752,021,072,936,960 (approximately 6.67 × 10²¹) valid complete Sudoku grids. This is still incomprehensibly large—if you enumerated one trillion grids per second, it would take millions of years to list them all.

Why backtracking works: Despite this vast search space, backtracking with constraint propagation can solve most Sudoku puzzles in milliseconds. The key insight is that we don't explore the full space—we prune aggressively. Each constraint violation discovered early eliminates entire subtrees of the search space, and each digit placement triggers cascading constraint propagation that often forces further placements.

SUDOKU SEARCH SPACE ANALYSIS
 
Naïve upper bound (ignoring constraints):
  9^81 = 1.97 × 10^77 possible configurations
 
Valid complete Sudoku grids:
  6,670,903,752,021,072,936,960 ≈ 6.67 × 10^21
 
Reduction factor:
  10^77 / 10^21 = 10^56 (constraints eliminate 99.999...% of configurations)
 
For a typical puzzle with 25 given cells:
  - 56 cells to fill
  - Naïve: 9^56 ≈ 10^53 configurations
  - With constraint propagation: Often <10,000 nodes explored
  - Reduction: >10^49 nodes pruned!
 
This dramatic pruning is why backtracking with 
constraint propagation is so effective.

The Pruning Imperative

The numbers above illustrate a critical lesson: brute force is not an option. Any algorithm that doesn't aggressively prune the search space will never terminate on Sudoku-sized problems. This is why constraint propagation and intelligent backtracking are not just optimizations—they're essential for feasibility.

Visualizing the search tree:

Imagine the search process as exploring a tree where:

The root represents the initial puzzle with given clues
Each internal node represents a partial assignment (some cells filled, others empty)
Each edge represents choosing a value for the next empty cell
Each leaf is either a complete valid solution or a dead end (constraint violation)

The goal of backtracking is to navigate this tree efficiently, cutting off dead-end branches as early as possible. The earlier we detect a constraint violation, the more of the tree we avoid exploring. This is the essence of pruning—using constraints to discard impossible configurations before fully exploring them.

Deep Dive: Types of Constraints in Sudoku

While we've identified Sudoku's three constraint types (rows, columns, boxes), a deeper analysis reveals subtle differences in how these constraints interact and how they can be exploited for solving:

Constraint Properties

•Unary Constraints: Single-variable restrictions. In Sudoku, pre-filled cells impose unary constraints: X[r][c] = v. These are trivially satisfied by initializing the domain to {v}.
•Binary Constraints: Restrictions between pairs of variables. Sudoku's inequality constraints (no two cells in a row/column/box can have the same value) are binary: for cells X[i] and X[j] in the same scope, X[i] ≠ X[j].
•Global Constraints: Higher-order constraints involving many variables. AllDifferent is a global constraint—it expresses that all 9 cells in a row (or column or box) must have distinct values. While reducible to pairwise binary constraints, the global view enables more powerful inference.

Binary vs. Global Constraint Representation

A single row constraint 'AllDifferent(X[r][0],...,X[r][8])' can be decomposed into C(9,2) = 36 binary constraints of the form X[r][i] ≠ X[r][j]. While logically equivalent, the global view enables inference that binary constraints miss—for example, if three cells in a row can only contain {1,2,3}, those three values are unavailable to other cells, even without knowing which cell gets which.

Constraint propagation and arc consistency:

When we assign a value to a cell, we must propagate this information through all constraints involving that cell. This process, called constraint propagation, reduces the domains of related cells.

The most common form of constraint propagation in Sudoku is Arc Consistency (AC): for every pair of constrained cells (A, B), every value in A's domain must have at least one compatible value in B's domain. If not, that value can be removed from A's domain.

For Sudoku specifically, when cell A is assigned value v:

Remove v from the domains of all 20 peer cells
If any peer's domain becomes empty, we have a contradiction (backtrack!)
If any peer's domain becomes a singleton {w}, that cell is forced to w (propagate further!)

This cascading propagation is what makes Sudoku solving fast—each decision triggers automatic inferences that often solve large portions of the puzzle without any guessing.

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
def propagate(board, domains, row, col, value):
    """
    Propagate the assignment of 'value' to cell (row, col).
    Removes 'value' from the domains of all peer cells.
    
    Returns:
        True if propagation succeeds (no domain becomes empty)
        False if a contradiction is detected (some domain becomes empty)
    """
    # The 20 peers of cell (row, col)
    peers = get_peers(row, col)
    
    for peer_row, peer_col in peers:
        domain = domains[peer_row][peer_col]
        
        if value in domain:
            domain.remove(value)
            
            if len(domain) == 0:
                # Contradiction: this peer has no valid values left
                return False
            
            if len(domain) == 1:
                # Forced assignment: only one value possible
                forced_value = next(iter(domain))
                board[peer_row][peer_col] = forced_value
                
                # Recursively propagate this forced assignment
                if not propagate(board, domains, peer_row, peer_col, forced_value):
                    return False
    
    return True
 
def get_peers(row, col):
    """Returns the 20 peer cells that constrain cell (row, col)."""
    peers = set()
    
    # Row peers
    for c in range(9):
        if c != col:
            peers.add((row, c))
    
    # Column peers
    for r in range(9):
        if r != row:
            peers.add((r, col))
    
    # Box peers
    box_row, box_col = 3 * (row // 3), 3 * (col // 3)
    for r in range(box_row, box_row + 3):
        for c in range(box_col, box_col + 3):
            if (r, c) != (row, col):
                peers.add((r, c))
    
    return peers

Constraint Satisfaction Solving Strategies

Solving a CSP like Sudoku combines constraint propagation with search. The art lies in balancing these two components. Let's examine the key strategies:

Constraint Propagation

•Domain Reduction: When a value is assigned, eliminate it from peer domains
•Naked Singles: If a cell's domain has one value, it's forced
•Hidden Singles: If a value can only go in one cell within a unit, it's forced
•Pairs/Triples: If N cells in a unit share exactly N possible values, eliminate those values elsewhere

Search Strategies

•Backtracking: Try values, undo if contradiction found
•Variable Ordering: Choose which cell to fill next (MRV heuristic)
•Value Ordering: Choose which value to try first (LCV heuristic)
•Intelligent Backjumping: Skip irrelevant decisions when backtracking

The propagation-search spectrum:

At one extreme, we could use pure propagation: apply sophisticated inference rules until no more deductions are possible, then hope the puzzle is solved. At the other extreme, we could use pure search: guess values and backtrack on failures without any inference.

In practice, the optimal approach lies in between:

Initial propagation: Apply basic constraint propagation to the given clues, often solving 'easy' puzzles entirely without search.
Search with propagation: For harder puzzles, interleave search (guessing) with propagation. After each guess, propagate extensively before making the next guess.
Early failure detection: The goal is to detect constraint violations as early as possible. Aggressive propagation after each guess quickly reveals dead ends, enabling early backtracking.

The more effective your propagation, the smaller the search tree becomes. This trade-off—spending time on inference versus spending time on search—is a fundamental tension in CSP solving.

The Power of Inference

Human Sudoku experts pride themselves on solving puzzles 'without guessing'—they apply increasingly sophisticated logical rules (X-Wing, Swordfish, XY-Chains, etc.) to deduce all cells. This is the propagation-heavy approach. Computers, being faster at trial-and-error, can afford to guess more liberally. But even computer solvers benefit enormously from strong propagation—it's the difference between exploring 10 nodes and 10,000.

From Theory to Algorithm

Now we connect the CSP framework to a concrete algorithmic approach. The key insight is that solving Sudoku is equivalent to finding a consistent, complete assignment of values to variables that satisfies all constraints.

Algorithmic translation:

Initialization: Parse the puzzle, creating domains for each cell. Pre-filled cells get singleton domains; empty cells get {1,...,9}.
Initial propagation: Propagate all given clues. For each pre-filled cell, remove its value from peer domains. If any domain becomes empty, the puzzle is unsolvable.
Search loop: While there exist cells with non-singleton domains:
- Select an unassigned cell (variable selection heuristic)
- For each value in its domain (value ordering heuristic):
  - Tentatively assign the value
  - Propagate consequences
  - If no contradiction: recurse to solve remainder
  - If contradiction or recursive failure: undo and try next value
- If all values fail: backtrack to previous decision
Termination: When all cells have singleton domains, we have a solution. If we backtrack past the first decision point with no remaining options, the puzzle has no solution.

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
def solve_sudoku_csp(puzzle):
    """
    Solve Sudoku using the CSP framework.
    
    1. Initialize domains from puzzle
    2. Apply initial constraint propagation
    3. Use backtracking search with propagation for unresolved cells
    """
    # Step 1: Initialize
    domains = initialize_domains(puzzle)
    
    # Step 2: Initial propagation
    for row in range(9):
        for col in range(9):
            if puzzle[row][col] != 0:  # Given clue
                if not propagate(domains, row, col, puzzle[row][col]):
                    return None  # Unsolvable: initial state is inconsistent
    
    # Step 3: Backtracking search
    return backtrack_search(puzzle, domains)
 
def backtrack_search(puzzle, domains):
    """Recursive backtracking with constraint propagation."""
    # Find an unassigned cell
    cell = select_unassigned_cell(puzzle, domains)
    
    if cell is None:
        # All cells assigned - solution found!
        return puzzle
    
    row, col = cell
    
    # Try each value in the cell's domain
    for value in order_domain_values(domains[row][col]):
        # Make a copy of domains for this branch
        domains_copy = deep_copy(domains)
        
        # Tentative assignment
        puzzle[row][col] = value
        domains_copy[row][col] = {value}
        
        # Propagate and check consistency
        if propagate(domains_copy, row, col, value):
            # No contradiction - recurse
            result = backtrack_search(puzzle, domains_copy)
            if result is not None:
                return result
        
        # Failed - undo assignment
        puzzle[row][col] = 0
    
    # All values failed - backtrack
    return None

The elegance of this approach:

Notice how naturally the CSP framework translates to the algorithm. We're not writing ad-hoc puzzle logic—we're implementing a general CSP solver that happens to be configured for Sudoku. The same structure, with different constraint definitions, could solve any CSP.

This generality is both intellectually satisfying and practically valuable. When you encounter a new constraint satisfaction problem, you don't start from scratch—you adapt the framework, defining variables, domains, and constraints specific to your problem while reusing the search and propagation machinery.

CSP Hardness and Complexity

Understanding the theoretical complexity of Sudoku provides insight into why certain puzzles are harder than others and why our algorithmic techniques are necessary:

NP-Completeness:

Generalized Sudoku (n²×n² grids with n×n boxes) is NP-Complete. This means:

Any proposed solution can be verified in polynomial time (just check all constraints)
No known polynomial-time algorithm solves all instances
It's as hard as the hardest problems in NP (SAT, graph coloring, etc.)

For standard 9×9 Sudoku, the fixed size means worst-case complexity is technically O(1)—but the hidden constant is astronomical. In practice, we care about average-case behavior, which depends heavily on puzzle characteristics.

Factors Affecting Sudoku Difficulty
Factor	Effect on Difficulty	Why
Number of given clues	Fewer clues → generally harder	Larger search space, more ambiguity
Distribution of clues	Clustered clues → often harder	Less initial propagation success
Required logic level	Advanced techniques → harder	Simple propagation insufficient
Number of solutions	Multiple solutions → structurally easier	More valid paths exist
Constraint graph structure	Symmetric constraints → variable	Can help or hurt depending on pattern

The Minimum Clue Problem

It has been proven (McGuire, 2012) that the minimum number of clues for a unique-solution Sudoku is 17. Puzzles with fewer clues either have multiple solutions or no solutions. These 17-clue puzzles represent some of the hardest instances because they leave maximum ambiguity within the constraint structure.

Implications for our algorithm:

The NP-completeness result tells us that no matter how clever our algorithm, there exist Sudoku instances that will require exponential work. However, for the vast majority of 'natural' puzzles (those designed by humans to be solvable), intelligent constraint propagation combined with good heuristics makes solving practically instantaneous.

The key insight is that hard instances are rare in practice. Most puzzles have enough structure that propagation and light search suffice. Pathological cases exist (and are interesting academically) but are unlikely to be encountered in normal use.

Summary: Sudoku as the Canonical CSP

We've established a rigorous foundation for understanding Sudoku through the lens of Constraint Satisfaction Problems. Let's consolidate the key insights:

Key Takeaways

•CSP framework defines problems through variables, domains, and constraints—a structure that directly informs algorithm design.
•Sudoku maps perfectly to CSP: 81 cell variables, digit domains, and 27 AllDifferent constraints across rows, columns, and boxes.
•The search space is vast (~10⁷⁷ naïve configurations), making uninformed approaches infeasible. Constraints reduce this dramatically to ~10²¹ valid grids.
•Constraint propagation (domain reduction upon assignment) is the key efficiency mechanism, often solving puzzles without any guessing.
•Backtracking search explores choices systematically, undoing decisions that lead to contradictions and trying alternatives.
•The combination of propagation and search, with good heuristics, solves most puzzles in milliseconds despite theoretical NP-completeness.

Looking Ahead

Now that we understand Sudoku as a CSP and the theoretical framework for solving it, the next page focuses on the cell-by-cell exploration strategy—the heart of backtracking search. We'll examine how to systematically visit cells, choose values, and manage the recursive exploration of the search tree.

Why this matters beyond Sudoku:

The CSP perspective you've gained is remarkably general. Once you can model a problem as variables, domains, and constraints, you've unlocked a powerful arsenal of solving techniques. Scheduling, resource allocation, planning, configuration, and countless optimization problems yield to this same framework. Sudoku is our laboratory—the techniques transfer immediately to real-world problems that don't come with a 9×9 grid.