CSP Solver Walkthrough

Unit 4: Optimization and Constraint Satisfaction — CSP Solver Walkthrough

This walkthrough is an optional companion to the Sudoku CSP Solver Lab. Review it after completing and submitting your own solution.

Overview

This walkthrough presents complete implementations of all lab components, with explanations of the design choices and the combinatorial effects that make each addition dramatically more efficient.

The complete solver integrates three powerful techniques:

Technique What It Does Impact

AC-3

Propagates constraints to reduce domains

Often solves easy puzzles without any search

MRV

Chooses the most constrained variable first

~100x speedup on hard puzzles

Backtracking

Systematic search with early failure detection

Completeness guarantee

Part 1: CSP Formulation

Initialize Domains

def _initialize_domains(self):
    """Set up initial domains for all cells."""
    for i in range(self.size):
        for j in range(self.size):
            if self.board[i][j] == 0:
                self.domains[(i, j)] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
            else:
                self.domains[(i, j)] = {self.board[i][j]}

Pre-filled cells get a domain of size 1 — a singleton set containing their value. This allows is_consistent() and ac3() to treat them uniformly with empty cells without special cases.

Using Python set (not list) for domains is important: removing a value from a set is O(1), while removing from a list is O(n). AC-3 removes many values from many domains, so this choice matters for performance.

Get Neighbors

def get_neighbors(self, cell):
    """Return all cells constrained with cell."""
    row, col = cell
    neighbors = set()

    # Same row
    for j in range(self.size):
        if j != col:
            neighbors.add((row, j))

    # Same column
    for i in range(self.size):
        if i != row:
            neighbors.add((i, col))

    # Same 3×3 box
    box_row = (row // 3) * 3
    box_col = (col // 3) * 3
    for i in range(box_row, box_row + 3):
        for j in range(box_col, box_col + 3):
            if (i, j) != cell:
                neighbors.add((i, j))

    return neighbors  # exactly 20 cells for every interior cell

Why exactly 20 neighbors?

Row: 8 cells (9 total minus self) Column: 8 cells (9 total minus self) Box: 8 cells (9 total minus self)

But the cell at the intersection of row and box is counted twice, and same for column and box. Using a set automatically eliminates these duplicates.

The result: every cell in a 9×9 Sudoku has exactly 20 unique neighbors. For corner and edge cells, the geometry is different but the count is still 20 (the three groups overlap more at the edges, but still sum to 20 unique cells).

Check Consistency

def is_consistent(self, cell, value):
    """Check if assigning value to cell would violate any constraint."""
    for neighbor in self.get_neighbors(cell):
        if len(self.domains[neighbor]) == 1:
            if list(self.domains[neighbor])[0] == value:
                return False
    return True

A neighbor is "assigned" when its domain has been reduced to a single value. We check only assigned neighbors because unassigned neighbors haven’t committed to any value yet — conflicts with them will be detected later.

list(self.domains[neighbor])[0] converts the singleton set to a list and takes the first (only) element. Alternatively: next(iter(self.domains[neighbor])) is more idiomatic Python.

Part 2: Backtracking Search

def backtracking_search(self):
    return self._backtrack_basic()

def _backtrack_basic(self):
    # Find an unassigned variable
    cell = self.select_unassigned_variable_basic()
    if cell is None:
        return True  # all assigned -- solution found

    original_domain = self.domains[cell].copy()

    for value in original_domain:
        if self.is_consistent(cell, value):
            self.domains[cell] = {value}             # assign
            self.backtracks_basic += 1

            if self._backtrack_basic():
                return True

            self.domains[cell] = original_domain.copy()  # undo

    return False  # no valid value found

Why copy the domain before iterating?

We iterate over original_domain rather than self.domains[cell] because we modify self.domains[cell] during the loop. If we iterated over the live domain, changing it mid-loop would corrupt the iteration.

The backtracking restoration:

When recursion fails, self.domains[cell] = original_domain.copy() restores the domain to its pre-assignment state. This is correct because basic backtracking (without forward checking) does not modify any other cell’s domain during assignment. Only this cell’s domain changes.

Part 3: MRV Variable Selection

def select_unassigned_variable_mrv(self):
    """Choose unassigned variable with smallest domain (MRV + degree tiebreaking)."""
    unassigned = [(cell, len(domain))
                  for cell, domain in self.domains.items()
                  if len(domain) > 1]

    if not unassigned:
        return None

    # Find minimum domain size
    min_size = min(size for _, size in unassigned)

    # Among tied cells, use degree heuristic (most unassigned neighbors)
    candidates = [cell for cell, size in unassigned if size == min_size]

    if len(candidates) == 1:
        return candidates[0]

    # Degree heuristic: count unassigned neighbors
    def degree(cell):
        return sum(1 for n in self.get_neighbors(cell)
                   if len(self.domains[n]) > 1)

    return max(candidates, key=degree)

List comprehension approach:

Building the unassigned list with a comprehension is more Pythonic and efficient than a nested loop. We compute domain sizes once and reuse them for both finding min_size and building candidates.

Degree heuristic as a secondary criterion:

The degree heuristic only runs when there are ties — the if len(candidates) == 1: return candidates[0] short-circuit skips the degree computation for the common case. This is important because get_neighbors() is called for every candidate, and doing this unnecessarily would slow down the algorithm.

Performance impact:

On the Easy Sudoku test puzzle: * Basic selection (first unassigned): ~42 backtracks * MRV selection: ~3 backtracks

MRV detects conflicts earlier because it always attacks the most constrained cell first.

Part 4: AC-3 Algorithm

REVISE

def revise(self, xi, xj):
    """Make arc (xi → xj) consistent. Remove unsupported values from xi."""
    revised = False
    for x in list(self.domains[xi]):         # copy to allow safe removal
        # For all-different: x has support if xj has any value != x
        if not any(y != x for y in self.domains[xj]):
            self.domains[xi].remove(x)
            revised = True
    return revised

The all-different support condition:

For Sudoku’s all-different constraint, value x from xi lacks support in xj if every value in xj’s domain equals x. This only happens when xj’s domain = {x} (a singleton with the same value).

So the check simplifies to:

if self.domains[xj] == {x}:
    self.domains[xi].discard(x)
    revised = True

Both implementations are correct; the second is more efficient for large domains.

Why list(self.domains[xi])?

We cannot iterate over a set while removing elements from it. Converting to a list first creates a snapshot of the domain to iterate over, while the actual set self.domains[xi] is safely modified.

AC-3

def ac3(self):
    """Enforce arc consistency using AC-3."""
    from collections import deque

    # Initialize queue with all arcs
    queue = deque()
    for cell in self.domains:
        for neighbor in self.get_neighbors(cell):
            queue.append((cell, neighbor))

    while queue:
        xi, xj = queue.popleft()

        if self.revise(xi, xj):
            if len(self.domains[xi]) == 0:
                return False             # empty domain: contradiction

            # xi's domain shrank -- re-check all arcs pointing to xi
            for xk in self.get_neighbors(xi):
                if xk != xj:
                    queue.append((xk, xi))

    return True

Why re-add arcs to the queue?

When xi’s domain shrinks, values that previously had support from xi may now lack it. Re-adding (xk, xi) for all neighbors xk of xi ensures those arcs are re-checked.

Queue vs. stack?

Using a deque (FIFO queue) rather than a stack (LIFO) does not affect correctness, but typically leads to better propagation in practice. FIFO processes arcs in the order they were added, which tends to spread constraint effects more evenly through the graph.

Time complexity:

Each arc (xi, xj) can be added to the queue at most d times (once per value removed from xi’s domain, where d is the initial domain size). There are O(c) arcs total. Each REVISE call takes O(d²) in the worst case. Total: O(c × d × d²) = O(cd³).

For Sudoku: c = 20 × 81 = 1,620 arcs, d ≤ 9. This is very fast even in the worst case.

Part 5: Complete Solver

def solve_sudoku(self):
    """Integrated solver: AC-3 preprocessing + MRV backtracking."""
    # Phase 1: AC-3 preprocessing
    if not self.ac3():
        return False                     # contradiction detected

    # Check if AC-3 solved everything
    if all(len(d) == 1 for d in self.domains.values()):
        return True                      # solved without search

    # Phase 2: Backtracking with MRV
    return self._backtrack_mrv()

def _backtrack_mrv(self):
    cell = self.select_unassigned_variable_mrv()
    if cell is None:
        return True

    original_domain = self.domains[cell].copy()

    # Save entire domain state for rollback (AC-3 modifies many domains)
    saved_domains = {c: d.copy() for c, d in self.domains.items()}

    for value in sorted(original_domain):
        if self.is_consistent(cell, value):
            self.domains[cell] = {value}
            self.backtracks += 1

            # Run AC-3 after each assignment (MAC algorithm)
            if self.ac3():
                result = self._backtrack_mrv()
                if result:
                    return True

            # Restore full domain state (AC-3 may have modified many domains)
            for c, d in saved_domains.items():
                self.domains[c] = d.copy()

    return False

Saving and restoring all domains:

Unlike basic backtracking, the MRV + AC-3 solver must save all domains before each assignment, not just the assigned variable’s domain. When AC-3 runs after an assignment, it may reduce the domains of many other variables. If that assignment ultimately fails, all those reductions must be undone.

This is called a domain store with backtracking or chronological backtracking over domain assignments.

More sophisticated implementations use dynamic backtracking or conflict-directed backjumping to avoid redundant work, but the approach above is correct and efficient enough for 9×9 Sudoku.

Performance Results

Puzzle Technique Time Backtracks

Easy

AC-3 only (no search needed)

< 0.001s

0

Medium

AC-3 + MRV backtracking

< 0.05s

~8

Hard

AC-3 + MRV backtracking

< 0.3s

~47

The dramatic performance comes from the combination of techniques:

  • AC-3 alone reduces domains so much that easy puzzles require no search at all

  • MRV ensures that when search is needed, the hardest variables are tackled first

  • Together, they collapse the 9^81 ≈ 2 × 10^77 naive state space into tens of backtracks

This is the power of the CSP framework: general-purpose algorithms that exploit problem structure automatically.

Next: Unit 4 Wrap-Up →

Lab code adapted from aima-python, MIT License, Copyright 2016 aima-python contributors.

This work is licensed under CC BY-SA 4.0.