Sudoku as Constraint Search

Each blank is a variable with candidates 1 through 9. Rows, columns, and 3-by-3 boxes must contain no repeated digit. This is a constraint satisfaction problem (CSP).

Compare plain backtracking with a solver that combines inference and backtracking. Run the cells in order with Matplotlib installed. The saved results are specific to these puzzles, not a benchmark across Sudoku instances.

Imports and Puzzle

The puzzle is a list of nine row lists. Zero represents an unassigned cell, not a Sudoku digit. The nonzero entries are fixed clues.

import copy
from collections import deque

import matplotlib.pyplot as plt
import matplotlib.patches as patches

# show a sudoku problem
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]
]

Draw the Grid

The helper writes only nonzero entries, draws thin cell boundaries, and emphasizes each 3-by-3 box. The vertical coordinate is flipped so list row 0 appears at the top. Drawing does not validate a solution.

def draw_puzzle(puzzle):
    fig, ax = plt.subplots(figsize=(3, 3))
    ax.set_aspect('equal')
    ax.set_xlim(0, 9)
    ax.set_ylim(0, 9)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.add_patch(patches.Rectangle((0, 0), 9, 9, fill=False))
    for i in range(9):
        for j in range(9):
            if puzzle[i][j] != 0:
                ax.text(j + 0.5, 8.5 - i, str(puzzle[i][j]), ha='center', va='center')
    for i in range(3):
        for j in range(3):
            ax.add_patch(patches.Rectangle((3 * j, 3 * i), 3, 3, fill=False
                , linewidth=2))
    for i in range(8):
        ax.add_patch(patches.ConnectionPatch((i + 1, 0), (i + 1, 9), 'data', 'data'))
        ax.add_patch(patches.ConnectionPatch((0, i + 1), (9, i + 1), 'data', 'data'))
    plt.show()

Inspect the Starting State

Choose one blank and eliminate digits already present in its row, column, and box. That manual candidate test is what the next helper automates.

Example answer

Using zero-based indices, choose (0, 2). Its row excludes 3, 5, and 7; its column excludes 8; and its box excludes 3, 5, 6, 8, and 9. The remaining candidates are 1, 2, and 4. This is a local legality check, not a guarantee that all three candidates extend to a full solution.

draw_puzzle(puzzle)

Check a Candidate

is_valid(puzzle, i, j, n) checks whether digit n conflicts with an existing entry in the row, column, or box of a blank cell. Integer division identifies the upper-left corner of the box.

The counter records recursive calls; success_flag avoids printing the solution repeatedly as recursion unwinds. Reset both before repeating the plain solver.

def is_valid(puzzle, i, j, n):
    for k in range(9):
        if puzzle[i][k] == n or puzzle[k][j] == n:
            return False
    for k in range(3):
        for l in range(3):
            if puzzle[(i // 3) * 3 + k][(j // 3) * 3 + l] == n:
                return False
    return True

success_flag = False
num = 0

Backtrack Through Assignments

The solver chooses the first blank in row-major order and tries digits from 1 through 9. A legal digit is written into the board before recursion. If the recursive call fails, the cell is reset to zero before trying another digit.

No blanks means success. Exhausting candidates at a blank means failure. This implementation assumes the supplied clues are valid; it is not a separate validator for arbitrary filled boards. The recursion mutates its argument, so later runs pass a deep copy.

def solve(puzzle):
    global success_flag, num
    num += 1
    for i in range(9):
        for j in range(9):
            if puzzle[i][j] == 0:
                for n in range(1, 10):
                    if is_valid(puzzle, i, j, n):
                        puzzle[i][j] = n
                        if solve(puzzle):
                            if not success_flag:
                                print(f"Solved. Recursive calls: {num:,}.")
                                draw_puzzle(puzzle)
                                success_flag = True
                            return True
                        puzzle[i][j] = 0
                return False
    return True

Represent Candidate Domains

Every coordinate maps to a set of candidates. Blank cells initially allow all digits; clue cells begin with a singleton set. make_domains creates a fresh dictionary for each puzzle and checks the 9-by-9 shape and digit range. Conflicting clues are detected during inference.

A fixed cell keeps its singleton domain. An empty domain always means failure; it is never used to mark a processed cell.

all_cells = [(i, j) for i in range(9) for j in range(9)]

def make_domains(puzzle):
    if len(puzzle) != 9 or any(len(row) != 9 for row in puzzle):
        raise ValueError("The puzzle must have 9 rows and 9 columns.")
    if any(type(n) is not int or not 0 <= n <= 9
           for row in puzzle for n in row):
        raise ValueError("Entries must be integers from 0 through 9.")
    return {
        (i, j): {puzzle[i][j]} if puzzle[i][j] else set(range(1, 10))
        for i, j in all_cells
    }

possible_values = make_domains(puzzle)

Find the Peer Cells

Peers share a row, column, or box with a cell. Set union removes duplicates where those groups overlap. The cell itself is excluded, leaving 20 distinct peers. Sorting the peers later makes the propagation order reproducible.

def peers(i, j):
    row = {(i, k) for k in range(9)}
    column = {(k, j) for k in range(9)}
    box = {(r, c)
           for r in range(i // 3 * 3, i // 3 * 3 + 3)
           for c in range(j // 3 * 3, j // 3 * 3 + 3)}
    return (row | column | box) - {(i, j)}

Remove an Assigned Digit from Peers

infer removes the assigned digit from each peer’s domain. If a peer loses its last candidate, it returns False. Otherwise it returns True, meaning this deletion step found no contradiction. It does not mean the puzzle is solved.

Because the source cell is not its own peer, its singleton remains intact. Two conflicting singleton clues make one peer’s domain empty and are rejected.

def infer(possible_values, i, j, n):
    for cell in sorted(peers(i, j)):
        if n in possible_values[cell]:
            possible_values[cell].remove(n)
            if not possible_values[cell]:
                return False
    return True

Propagate Forced Values

propagate puts singleton cells into a queue. For each one, it writes the forced digit to the board and removes that digit from peers. Newly forced peers join the queue, so propagation continues until no forced cells remain to process.

The local processed set avoids propagating the same cell twice during this call. Domains remain nonempty unless a contradiction is found. This helper mutates its arguments; the search function below gives it branch-local copies.

def propagate(puzzle, possible_values):
    if any(not possible_values[cell] for cell in all_cells):
        return False
    queue = deque(cell for cell in all_cells
                  if len(possible_values[cell]) == 1)
    processed = set()
    while queue:
        cell = queue.popleft()
        if cell in processed:
            continue
        i, j = cell
        n = next(iter(possible_values[cell]))
        if puzzle[i][j] not in (0, n):
            return False
        puzzle[i][j] = n
        processed.add(cell)
        if not infer(possible_values, i, j, n):
            return False
        for peer in sorted(peers(i, j)):
            if len(possible_values[peer]) == 1 and peer not in processed:
                queue.append(peer)
    return True

Search When Propagation Stalls

solve_reduce first propagates on copied state. If every domain is singleton, the board is complete. Otherwise, minimum remaining values (MRV) chooses an unresolved cell with the fewest candidates. Values are tried in increasing order.

Each guess restricts a fresh child domain to {n}. The recursive call propagates that decision before making another guess. If it fails, discard the child and try the next value; the parent’s board and domains stay intact. The function returns False only after propagation fails or every candidate branch fails.

num_reduce = 0

def solve_reduce(puzzle, possible_values):
    global num_reduce
    num_reduce += 1
    copy_possible_values = copy.deepcopy(possible_values)
    copy_puzzle = copy.deepcopy(puzzle)
    if not propagate(copy_puzzle, copy_possible_values):
        return False
    unresolved = [cell for cell in all_cells
                  if len(copy_possible_values[cell]) > 1]
    if not unresolved:
        print(f"Solved. Recursive calls: {num_reduce:,}.")
        draw_puzzle(copy_puzzle)
        return True
    cell = min(unresolved, key=lambda cell: len(copy_possible_values[cell]))
    for n in sorted(copy_possible_values[cell]):
        child_domains = copy.deepcopy(copy_possible_values)
        child_domains[cell] = {n}
        if solve_reduce(copy_puzzle, child_domains):
            return True
    return False

Run Plain Backtracking

Reset the counter and output flag before each run. The deep copy protects the original clues. This puzzle takes 4,209 recursive calls with the row-major solver; calls are not the same as individual constraint checks.

success_flag = False
num = 0
solve(copy.deepcopy(puzzle))
Solved. Recursive calls: 4,209.

True

Run Inference and Backtracking

The queue solves this supplied puzzle through forced values within one search call, without guessing. The same function can branch when propagation stalls. One propagation pass can do many candidate checks, so recursive-call counts are not a direct timing comparison. The final True is the returned success flag.

num_reduce = 0
solve_reduce(puzzle, possible_values)
Solved. Recursive calls: 1.

True

Test a Puzzle That Needs Guessing

An empty grid has no singleton domains, so propagation alone cannot start. The solver must restrict a guessed cell to one digit before recursion. It returns the first valid completion; an empty grid has many solutions.

Each recursive choice fixes one unresolved cell. Every candidate receives its own branch-local domains.

empty_puzzle = [[0] * 9 for _ in range(9)]
num_reduce = 0
solve_reduce(empty_puzzle, make_domains(empty_puzzle))
Solved. Recursive calls: 48.

True

Compare the Two Approaches

  • Confirm that every original clue is unchanged in the displayed solutions.
  • Trace where plain backtracking undoes a choice and where inference removes a candidate.
  • Explain why choosing a cell with few remaining values can reduce branching. This is the minimum remaining values (MRV) heuristic.
  • Find where a guessed value changes its domain and explain why a failed branch cannot change its parent.
Answers and discussion
  1. Check the clues independently of the blanks. Every initially nonzero entry must equal the corresponding final entry. For example, the original top-row 5, 3, and 7 retain their positions. Plain backtracking writes only into zeros; the inference version initializes each clue with exactly its given digit. A complete solution also needs each row, column, and box to contain digits 1 through 9.
  2. Undo versus eliminate. In solve, the line puzzle[i][j] = 0 restores a blank after a recursive branch fails. In infer, .remove(n) deletes an assigned digit from peer domains. The inference solver instead uses copied boards and domains, so it discards a failed child rather than undoing changes in shared state.
  3. MRV exposes difficult choices early. A cell with two candidates creates at most two branches, while one with eight creates up to eight. A singleton is forced, and an unresolved empty domain signals failure. MRV often reduces wasted search by finding constrained decisions and contradictions early, but does not guarantee the smallest search tree on every puzzle.
  4. A guess changes its domain. The line child_domains[cell] = {n} records the decision. The recursive call propagates it on a copied board and copied domains. No set is shared with the parent, and each candidate starts with a fresh copy. Restricting an unresolved domain and propagating its singleton makes progress; failure discards that branch’s deletions.

Takeaway: inference can avoid search, but a general solver still needs correct state management and branching when propagation stalls.